欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

二叉树题目总结(Java版本)

程序员文章站 2022-05-20 21:34:34
...

二叉树总结


1. 重建二叉树

import java.util.*;
public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        if(pre.length == 0||in.length == 0){
            return null;
        }
        int curNode = pre[0];
        TreeNode node = new TreeNode(curNode);
        // 遍历数组,找到父节点在中序中的位置
        // 递归的时候考虑终止条件,当前函数中的操作,如何递,归什么回去,归回去的赋值给谁
        for(int i=0; i<in.length; i++){
            if(in[i]==pre[0]){
                node.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i+1), Arrays.copyOfRange(in, 0, i));
                node.right =reConstructBinaryTree(Arrays.copyOfRange(pre, i+1, pre.length),Arrays.copyOfRange(in, i+1, in.length));
            }
        }
        return node;
    }
}

2. 树的子结构

public class Solution {
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        boolean found = false;
        if(root2==null||root1==null) return false;
        // 首先找到开始的点
        if(root1.val==root2.val) found = StartSearch(root1, root2);
        if(!found){
             found = (HasSubtree(root1.left, root2)||HasSubtree(root1.right, root2));
        }
        return found;
    }

    public boolean StartSearch(TreeNode root1, TreeNode root2){
        // 不管原树节点为不为空,都返回true
        if(root2==null) return true;
        // 如果原树已经空了,但子树没空,则返回false
        if(root1==null&&root2!=null) return false;
        // 如果两个值不相等,则返回false
        if(root1.val!=root2.val) return false;

        return StartSearch(root1.left, root2.left)&&StartSearch(root1.right, root2.right);

    }
}

3. 二叉树的镜像

public class Solution {
    public void Mirror(TreeNode root) {
        // 只需要递,不需要归
        if(root==null) return;
         exchange(root);  
        Mirror(root.left);
        Mirror(root.right);
    }

    public void exchange(TreeNode root){
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
    }
}

4. 从上到下打印二叉树

import java.util.*;
public class Solution {
    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
        ArrayList<Integer> result = new ArrayList<> ();
        Queue<TreeNode> queue = new LinkedList<> ();
        if(root==null) return result;
        queue.add(root);
        while(!queue.isEmpty()){
            TreeNode current = queue.poll();
            result.add(current.val);
            if(current.left!=null) queue.add(current.left);
            if(current.right!=null) queue.add(current.right);
        }
        return result;
    }
}

5. 二叉搜索树的后序遍历

public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence==null||sequence.length==0) return false;
        if(sequence.length==1) return true;
        // 开始递归
        return Check(sequence, 0, sequence.length-1);
    }
    // 找到左子树,判断左子树的所有结点是否小于根节点 
    public boolean Check(int[] sequence, int start, int end){
    // 终止条件
        if(end<=start) return true;
        int root = sequence[end];
        int p = end-1;
     // 左子树最后一个结点  
        while(p>=start&&sequence[p]>root){
            p--;
           }
    // 一旦左子树有结点小于根节点,返回false        
        for(int i=start; i<=p; i++){
            if(sequence[i]>root) return false;
        }
        // 搜索左右子树
        return Check(sequence, p+1, end-1)&&Check(sequence, start, p);

    }
}

6. 二叉树中和为某一值的路径

import java.util.ArrayList;
public class Solution {
// 设为全局变量比较简洁
    ArrayList<ArrayList<Integer>> result = new ArrayList<> ();
    ArrayList<Integer> temp = new ArrayList<Integer> ();
    // root为入口点,开始回溯
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
        int sum = 0;
        if(root==null) return result;
        backChecking(root, target, sum);
        return result;
    }
    // 回溯递归函数
    public void backChecking(TreeNode root, int target, int sum){
        if(root==null) {
             return;
        }
        sum += root.val;
        temp.add(root.val);
        // 添加条件,如果root==null再添加,那么可能会重复添加值到结果中
        if(root.left==null&&root.right==null&&sum==target){
                result.add(new ArrayList<Integer>(temp));
            }
        backChecking(root.left, target, sum);
        backChecking(root.right, target, sum);
        temp.remove(temp.size()-1);
    }
}

7. 二叉树的深度:递归和非递归版本

非递归

public class Solution {
    int count = 0;
    public int TreeDepth(TreeNode root) {
        if(root==null) return 0;
        return Math.max(TreeDepth(root.left),  TreeDepth(root.right))+1;
    }
}

递归

import java.util.*;
public class Solution {

    public int TreeDepth(TreeNode root) {
        if(root==null) return 0;
        Queue<TreeNode> queue = new LinkedList<>();
        int count = 0;
        // 重点是这儿,记录同一层的个数
        int nextCount = 1;
        int depth = 0;
        queue.add(root);
        while(!queue.isEmpty()){
            TreeNode top = queue.poll();
            count++;
            if(top.left!=null){
                queue.add(top.left);
            }
            if(top.right!=null){
                queue.add(top.right);
            }
            if(count==nextCount){
                nextCount = queue.size();
                count = 0;
                depth++;
            }
        }
     return depth;

    }
}

8.平衡二叉树:后序和先序遍历

public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        if(root==null) return true;
        int l = 0;
        int r = 0;
        if(root.left!=null){
            l = getDepth(root.left);
        }
        if(root.right!=null){
            r = getDepth(root.right);
        }
        if(l-r>1||r-l>1) return false;
        // 只要有一个false出现,则会返回false
        return IsBalanced_Solution(root.left)&IsBalanced_Solution(root.right);

    }

    public int getDepth(TreeNode root){
        if(root==null) return 0;
        return Math.max(getDepth(root.right), getDepth(root.left))+1;
        }

}

9. 二叉树的下一个结点

public class Solution {
    public TreeLinkNode GetNext(TreeLinkNode pNode)
    {
        if(pNode==null) return null;
        // 首先判断有没有右结点,有的话得找右结点最左边的结点
        if(pNode.right!=null){
            pNode = pNode.right;
            while(pNode.left!=null){
                pNode = pNode.left;
            }
            return pNode;
        }
        // 如果没有,则向上找到第一个左节点
        else{
            while(pNode.next!=null){
                if(pNode==pNode.next.left){
                    return pNode.next;
                }
                pNode = pNode.next;
            }
            // 如果找到根节点都没有找到,返回null
            return null;
        }
    }
}

10.对称的二叉树

与是否是子树问题有点像

public class Solution {
    public boolean isSymmetrical(TreeNode pRoot)
    {
        if(pRoot==null){
            return true;
        }
        return Search(pRoot.left, pRoot.right);
    }
    public boolean Search(TreeNode node1, TreeNode node2){
        if(node1==null&&node2!=null) return false;
        if(node1!=null&&node2==null) return false;
        if(node1==null&&node2==null) return true;
        if(node1.val!=node2.val) return false;
        return Search(node1.left, node2.right)&&Search(node1.right, node2.left);
    }
}

11. 按之字形打印二叉树

import java.util.*;
public class Solution {
    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        //首先按层遍历所有节点
        //先把根节点存到栈中,然后会出栈,然后记录左右节点,把左右当到第二个栈中,那么右先推出来,存右子节点,然后左节点到第一个栈。
        ArrayList<ArrayList<Integer>> result = new  ArrayList<ArrayList<Integer>>();
        if(pRoot==null) return result; 
        Stack<TreeNode> stack1=new Stack<>();
        Stack<TreeNode> stack2=new Stack<>();
        stack1.push(pRoot);
        while(!stack1.isEmpty()||!stack2.isEmpty()){
            ArrayList<Integer> temp = new ArrayList<Integer>();
            if(!stack2.isEmpty()){    
                while(!stack2.isEmpty()){
                    TreeNode node = stack2.pop();
                    temp.add(node.val);
                    if(node.right!=null) stack1.push(node.right);
                    if(node.left!=null) stack1.push(node.left);

                }
            }
            else{
                while(!stack1.isEmpty()){
                    TreeNode node = stack1.pop();
                    temp.add(node.val);
                    if(node.left!=null) stack2.push(node.left);
                    if(node.right!=null) stack2.push(node.right);

                }
            }
            result.add(new  ArrayList<Integer>(temp));

        }
        return result;
    }
}

12. 把二叉树打印多行

与求二叉树深度类似

public class Solution {
    ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        if(pRoot==null) return result;
        Queue<TreeNode> queue = new LinkedList<>();
        ArrayList<Integer> list = new ArrayList<Integer>();
        int count = 0;
        int size = 1;
        queue.add(pRoot);
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            list.add(node.val);
            count++;
            if(node.left!=null)  queue.add(node.left);
            if(node.right!=null)    queue.add(node.right);
            if(count==size){

                size = queue.size();
                count = 0;
                result.add(new ArrayList<Integer>(list));
                list = new ArrayList<Integer>();
            }
        }
        return result;
    }
}

13. 序列化二叉树

public class Solution {
    int index=0;
    StringBuilder builder = new StringBuilder();
    String Serialize(TreeNode root) {
        if(root!=null) builder.append(root.val+"!");
        else{
            return builder.append("#!").toString();
        }
        Serialize(root.left);
        Serialize(root.right);
        return builder.toString();
  }
    TreeNode Deserialize(String str) {
       if(str==null) return null;
       String[] nodes=str.split("!");
       if(index>=nodes.length) return null;
       if(nodes[index].equals("#")){
           index++;
           return null;
       }
       TreeNode node = new TreeNode(Integer.parseInt(nodes[index++]));
       node.left = Deserialize(str);
       node.right =  Deserialize(str);
       return node;
  }
}

14. 求第K小的数

递归

public class Solution {
   int index = 0; //计数器
    TreeNode KthNode(TreeNode root, int k)
    {
        if(root != null){ //中序遍历寻找第k个
            TreeNode node = KthNode(root.left,k);
            // 如果这两行去掉,我们仍然能找到第K大的数,但是没法return, 所以要想办法return
            if(node != null)
                return node;
            index ++;
            if(index == k)
                return root;
            node = KthNode(root.right,k);
            if(node != null)
                return node;
        }
        return null;
    }
}

非递归

import java.util.*;
public class Solution {
    TreeNode KthNode(TreeNode pRoot, int k)
    {   int index = 0;
        Stack<TreeNode> stack = new Stack<>();
        while(pRoot!=null||!stack.isEmpty()){
           while(pRoot!=null){
               stack.push(pRoot);
               pRoot = pRoot.left;
           }
           if(!stack.isEmpty()){
               pRoot = stack.pop();
               index++;
               if(index==k) return pRoot;
               pRoot = pRoot.right;
           }
        }
     return null;
    }
}

15. 先序, 中序, 后序的非递归实现

先序

 public void midOrder1(BinaryNode<AnyType> Node)
    {
        Stack<BinaryNode> stack = new Stack<>();
        // 当当前节点为空,且stack为空时不能进入循环
        while(Node != null || !stack.empty())
        {
            while (Node != null)
            {   System.out.println(Node.val);
                stack.push(Node);
                Node = Node.left;
            }
            if(!stack.empty())
            {
                Node = stack.pop();
                System.out.print(Node.element + "   ");
                Node = Node.right;
            }
        }
    }

中序

public void midOrder1(BinaryNode<AnyType> Node)
    {
        Stack<BinaryNode> stack = new Stack<>();
        // 当当前节点为空,且stack为空时不能进入循环
        while(Node != null || !stack.empty())
        {
            while (Node != null)
            {   System.out.println(Node.val);
                stack.push(Node);
                Node = Node.left;
            }
            if(!stack.empty())
            {
                Node = stack.pop();
                System.out.print(Node.element + "   ");
                Node = Node.right;
            }
        }
    }

后序

public void posOrder1(BinaryNode<AnyType> Node)
    {
        Stack<BinaryNode> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();
        int i = 1;
        while(Node != null || !stack1.empty())
        {
            while (Node != null)
            {
                stack1.push(Node);
                stack2.push(0);
                Node = Node.left;
            }

            while(!stack1.empty() && stack2.peek() == i)
            {
                stack2.pop();
                System.out.print(stack1.pop().element + "   ");
            }

            if(!stack1.empty())
            {
                stack2.pop();
                stack2.push(1);
                Node = stack1.peek();
                Node = Node.right;
            }
        }
    }

上一篇: 迷宫问题(bfs)

下一篇: 关键路径