二叉树必刷题-阿里云开发者社区

一、二叉树的前、中、后序遍历（递归和非递归）

递归代码的思想：通过左子树，右子树来进行重复调用函数

非递归的思想：先利用栈记录每个节点的位置，再控制打印顺序即可

1. 前序遍历

递归代码：

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        preorder(root,list);
        return list;
    }
    public void preorder(TreeNode root,List<Integer> list){
        if(root == null) return;
        list.add(root.val);
        preorder(root.left,list);
        preorder(root.right,list);
    }
}

非递归代码：

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        List<Integer> list = new ArrayList<>();
        TreeNode cur = root;
        while(cur != null || !stack.isEmpty()){
            while(cur != null){
                list.add(cur.val);
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.pop();//用弹出的节点记录其前后位置
            cur = top.right;
        }
        return list;
    }
}

2. 中序遍历

leetcode 94

递归代码：

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        inorder(root,list);
        return list;
    }
    public void inorder(TreeNode root,List<Integer> list){
        if(root == null) return;
        inorder(root.left,list);
        list.add(root.val);
        inorder(root.right,list);
    }
}

非递归代码：

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        List<Integer> list = new ArrayList<>();
        TreeNode cur = root;
        while(cur != null || !stack.isEmpty()){
            while(cur != null){
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            list.add(top.val);
            cur = top.right;
        }
         return list;
    }
}

3. 后序遍历

leetcode 145

递归代码：

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        postorder(root,list);
        return list;
    }
    public void postorder(TreeNode root,List<Integer> list){
        if(root == null) return;
        postorder(root.left,list);
        postorder(root.right,list);
        list.add(root.val);
    }
}

非递归代码：

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        List<Integer> list = new ArrayList<>();
        TreeNode cur = root;
        TreeNode flag = null;
        while(cur != null || !stack.isEmpty()){
            while(cur != null){
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.peek();
            if(top.right == null || top.right == flag){
                stack.pop();
                list.add(top.val);
                flag = top;
            }else{
                cur = top.right;
            }
        }
        return list;
    }
}

二、比较二叉树的特征

4. 判断两颗二叉树是否为相同的树

leetcode 102

要求：

① 两棵树的结构相等

② 两颗树的每个节点的值相等

思路：先把所有情况设想出来，再通过每一种情况分析出边界条件。

从头节点开始，通过边界条件 null 来判断树的结构是否相等，试想：如果中途有节点对应的值不相等，那么直接返回 false，反之，如果两棵树走到了的树的最后，一定走到了 null，那么此时两颗树的左子树或右子树一定相同了。

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if((p == null && q != null) || (p != null && q == null)){
            return false;
        }
        if(p == null && q == null){ //边界条件
            return true;
        }
        if(p.val != q.val){
            return false;
        }
        boolean ret1 = isSameTree(p.left,q.left);
        boolean ret2 = isSameTree(p.right,q.right);
        return  ret1 && ret2;
    }
}

5. 判断一棵树是不是另一棵树的子树

leetcode 572

思路：通过 isSame 函数来判断子树与另一棵树的左子树或右子树是否相同。

① 从头节点开始，先判断头结点对应的左子树和右子树，如果满足，就返回 true, 反之，就返回 false.

② 如果上述过程没有经历，那么接下来就判断子树是不是另一棵树其他双亲节点的左子树、右子树。

class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        //先判断根节点对应的树是不是和子树相等
        if( isSameTree(root,subRoot) ){
            return true;
        }
        if( (root == null && subRoot != null) || (root != null && subRoot == null) ){
            return false;
        }
        if(root == null && subRoot == null){ //边界条件
            return true;
        }
        return isSubtree(root.left,subRoot) || isSubtree(root.right,subRoot);
    }
    public boolean isSameTree(TreeNode p, TreeNode q){
        if( (p == null && q != null) || (p != null && q == null) ){
            return false;
        }
        if(p == null && q == null){ //边界条件
            return true;
        }
        if(p.val != q.val){
            return false;
        }
        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    }
}

6. 判断一棵树是不是对称二叉树

leetcode 101

思路：左子树的左值 = 右子树的右值，左子树的右值 = 右子树的左值

重新创建一个函数 judge( ) ，传参分别为左节点和右节点，注意边界条件。

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return judge(root.left, root.right);
    }
    public boolean judge(TreeNode l, TreeNode r){
        if(l == null && r == null){ //边界条件
            return true;
        }
        if( (l == null && r!= null) || (l != null && r == null) ){
            return false;
        }
        if(l.val != r.val){
            return false;
        }
        boolean ret1 = judge(l.left,r.right);
        boolean ret2 = judge(l.right,r.left);
        return ret1 &&  ret2;
    }
}

7. 求二叉树的最大深度

leecode 104

思路：Max( 左子树的深度，右子树的深度 ) + 1

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

8. 判断一棵树是否为平衡二叉树

思路：

① 若整个树为空，说明这个树也是一个平衡二叉树

② 若左子树和右子树之差为 ret ，那么 ret 的绝对值需要满足 <=1.

③ 整个二叉树需要判断平衡，其中的每个双亲节点对应的左右子树也要平衡，也就是说：这是一个子问题递归的思想。

leetcode 110

class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root == null) return true;
        int leftHeight = TreeHeight(root.left);//每个节点的左子树高度
        int rightHeight = TreeHeight(root.right);//每个节点的右子树高度
        //其中的每个双亲节点对应的左右子树也要平衡
        if(Math.abs( leftHeight - rightHeight) <= 1 
        && isBalanced(root.left) && isBalanced(root.right) )
        {
          return true;
        }else{
            return false;
        }
    }
    public int TreeHeight(TreeNode root){
        if(root == null) return 0;
        int l = TreeHeight(root.left);
        int r = TreeHeight(root.right);
        return Math.max(l, r) + 1;
    }
}

三、构建二叉树

9. 通过前序、中序数组构建二叉树

leetcode 105

思路：前序找根，中序来分。

① 定义数组下标 i，让 i 去遍历前序数组，不断地找根，每找到一个根节点（双亲节点），直接 new 一个对象。

② 定义数组下标 j，让 j 去遍历中序数组，通过 preorder[ i ] 来找到 inorder[ j ] ，通过 j 下标不断地分割左子树、右子树。

③ 定义数组下标 m, n，让 m 和 n 不断地转换，思想：让 m 和 n 分别不断地成为左子树和右子树的边界，当 n < m，那么直接返回 null，以此来控制递归返回。

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int m = 0;
        int n = inorder.length - 1;
        TreeNode root = createTree(preorder, inorder, m, n);
        return root;
    }
/**
  i - 用来遍历前序数组
  j - 用来遍历中序数组
  m, n- 用来控制左右子树边界
 */
    public int i = 0;
    public TreeNode createTree( int[] preorder, int[] inorder, int m, int n){
        if(n < m) return null;
        TreeNode root = new TreeNode(preorder[i]);//找到一个根，直接 new 一个对象
        int j = findIndex(inorder, preorder[i]);
        i++;
        root.left = createTree(preorder, inorder, m, j-1); //n = j-1，控制边界
        root.right = createTree(preorder, inorder, j+1, n);//m = j+1，控制边界
        return root;
    }
    //找到 inorder[j]
    public int findIndex( int[] inorder, int key){
        for(int j=0; j<inorder.length; j++){
            if(key == inorder[j]){
                return j;
            }
        }
        return -1;
    }

10. 通过中序、后序数组构建二叉树

leetcode 106

思路：后序找根，中序来分。

本题思想与上一题思想相同，唯一改变的就是：本题是先构建右子树，再构建左子树。因为在后序数组中，根节点的位置属于数组的最后一个元素，从而我们让 i-- 的时候，每次在中序数组中先拿到的都是右子树。其次，变量 i 的定义位置也需要注意！

class Solution {
    public int i = 0;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        int m = 0;
        int n = inorder.length - 1;
        i = postorder.length - 1;
        TreeNode root = createTree(inorder, postorder, m, n);
        return root;
    }
    public TreeNode createTree(int[] inorder, int[] postorder, int m, int n){
        if(n < m) return null;
        TreeNode root = new TreeNode(postorder[i]);
        int j = findIndex(inorder, postorder[i]);
        i--;
        root.right = createTree(inorder, postorder, j+1, n);
        root.left = createTree(inorder, postorder, m, j-1);
        return root;
    }
    public int findIndex(int[] inorder, int key){
        for(int j=0; j<inorder.length; j++){
            if(key == inorder[j]){
                return j;
            }
        }
        return -1;
    }
}

11. 通过字符串构建一棵二叉树

牛客网 KY11

思路：

在函数 initialTree( ) 中，遍历字符串，通过拿到字符串的每一个字符，来new 一个节点，构建二叉树的过程中遵循前序遍历，最终打印出来遵循中序遍历。

import java.util.*;
class TreeNode{
    public char val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(char val){
        this.val = val;
    }    
}
public class Main{
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);      
        while(scanner.hasNext()){
            String str = scanner.nextLine();
            TreeNode root = initialTree(str);
            inOrder(root);
        }
    }
    public static int i;
    public static TreeNode initialTree(String str){    
        TreeNode root = null;  
        if(str.charAt(i) == '#'){
            i++;
            return null;
        }
        root = new TreeNode ( str.charAt(i) );
        i++;
        root.left = initialTree(str);
        root.right = initialTree(str);
        return root;   
    }
    public static void inOrder(TreeNode root){
        if(root == null) return;
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }
}

四、将二叉树转换成其他结构

12. 将一棵二叉搜索树转换成一个升序的双向链表

牛客网 JZ36

思路：

① 由于二叉搜索树的左子树总是比双亲节点小，右子树总是比双亲节点大，这样一来，我们就可以进行中序遍历来改变 left 和 right 的指向。

② 定义一个前驱指针 prev，可以和 root 进行前后连接起来，prev 的右就是 root,

root 的左就是 prev，每次 prev 都要记录一下 root 的位置，以便下一次连接。

③ 通过已创建后的链表，我们让 pRootOfTree 一直往左走，直到拿到链表的头节点。

二叉搜索树（二叉排序树）：

public class Solution {
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null) return null;
        inOrder(pRootOfTree);
        //让根节点向左走，直至链表头节点
        while(pRootOfTree.left != null){
            pRootOfTree = pRootOfTree.left;
        }
        return pRootOfTree;
    }
    public TreeNode prev = null;
    public void inOrder(TreeNode root){
        if(root == null) return;
        inOrder(root.left);
        //进行改变 left 和 right 的指向
        root.left = prev;
        if(prev != null){
            prev.right = root;
        }
        prev = root;
        inOrder(root.right);      
    }
}

13. 根据二叉树创建字符串

leetcode 606

思路：采用前序遍历

① 如果一个双亲节点的左子树不为空，append( " ( " )

② 如果一个双亲节点左子树为空，右子树不为空，append( " ( ) " )

③ 当一个双亲节点的左子树走完返回的时候，需要判断右子树的节点空与否，若不为空，就 append( " ( " )

④ 当一个双亲节点左右子树都走完的时候，append( " ) " )

class Solution {
    public String tree2str(TreeNode root) {
        StringBuilder strb = new StringBuilder();
        treeToStr(root, strb);
        strb.deleteCharAt(strb.length()-1); //删除已拼接的最后一个数据
        return strb.toString();
    }
    public void treeToStr(TreeNode root, StringBuilder strb){
        if(root == null) return;
        strb.append(root.val);
        if(root.left != null){
            strb.append("(");
        }
        if(root.left == null && root.right != null){
            strb.append("()");
        }
        treeToStr(root.left, strb);
        if(root. right != null){
            strb.append("(");
        }
        treeToStr(root.right, strb);
        strb.append(")");
    }

14. 层序遍历

leetcode 102

思路：

利用队列这个数据结构进行记录每个节点的前后位置。

public void levelOrder(TreeNode root){
    if(root == null) return;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while(!queue.isEmpty()){
        root = queue.poll();
        System.out.print(root.val + " ");
        if(root.left != null){
            queue.offer(root.left);
        }
        if(root.right != null){
            queue.offer(root.right);
        }
    }
}

15. 寻找二叉树的最近公共祖先

leetcode 236

方法一思路：

① 如果根 root 就是 p 节点或者 q 节点，那么公共祖先就是 root

② 如果 p 和 q 节点都在 root 的左子树，那么公共祖先一定就是 root 左子树中的一个节点

③ 如果 p 和 q 节点都在 root 的右子树，那么公共祖先一定就是 root 右子树中的一个节点

④ 如果 p 和 q 节点一个在 root 的左子树，另一个在 root 的右子树，那么公共祖先一定就是 root

上面四种情况是针对于 root 这个根节点而言的！那么我们试着想一下：当 root 表示的是整个二叉树中的其中一个小的二叉树的根节点，那么上面四种情况也能够应用到此节点！这个时候我们就可以用递归来完成它！也就是说：子问题也需要考虑进去

方法二思路：

创建两个栈，分别为 stack1 和 stack2，将二叉树中根节点到 p 节点的路径放入stack1 中，将二叉树中根节点到 q 节点的路径放入 stack2 中。假设 stack1 比 stack2 中的元素多 k 个，那么我们就先移除这 k 个元素，之后再进行 stack1 和 stack2 的栈顶比较，相同的栈顶即为祖先节点。

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == p || root == q){
            return root;
        }    
        if(root == null){
            return null;
        }
        TreeNode l = lowestCommonAncestor(root.left,p,q);
        TreeNode r = lowestCommonAncestor(root.right,p,q);
        if( l != null && r != null){
          //p, q 分布在某个双亲节点两侧
            return root;
        }else if( l != null ){
          //p, q 分布在某个双亲节点左侧
            return l;
        }else if (r != null){
          //p, q 分布在某个双亲节点右侧
            return r;
        }else{
            return null;
        }        
    }
}

二叉树必刷题

一、二叉树的前、中、后序遍历（递归和非递归）

1. 前序遍历

2. 中序遍历

3. 后序遍历

二、比较二叉树的特征

4. 判断两颗二叉树是否为相同的树

5. 判断一棵树是不是另一棵树的子树

6. 判断一棵树是不是对称二叉树

7. 求二叉树的最大深度

8. 判断一棵树是否为平衡二叉树

三、构建二叉树

9. 通过前序、中序数组构建二叉树

10. 通过中序、后序数组构建二叉树

11. 通过字符串构建一棵二叉树

四、将二叉树转换成其他结构

12. 将一棵二叉搜索树转换成一个升序的双向链表

13. 根据二叉树创建字符串

14. 层序遍历

15. 寻找二叉树的最近公共祖先

热门文章

最新文章

相关电子书