三个经典例题

  • 通过三个例题了解解题模板，让你用模板越用越爽

    判断一棵树是否是满二叉树

    判断一棵树是否是平衡二叉树

    判断一棵树是否是搜索二叉树

模板

定义一个返回信息

1
2
3
4
5
6
7
8
9
10
private static class info{
       //  需要的信息可以有多个
       private int height; // 树的高度
       private int nodes;  // 树的节点个数

       info(int n, int h){
           this.height = h;
           this.nodes = n;
       }
   }

递归套路（认真看）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
private static info process(TreeNode head ){

        // 判断空树情况 
        if(head == null){
            return new info(0,0);
        }

        // 左子树收集信息
        info leftData = isFullTree(head.left);
        // 右子树收集信息
        info rightData = isFullTree(head.right);

        // 更新信息
        int nodes = leftData.nodes + rightData.nodes  + 1;
        int height = Math.max(leftData.height,rightData.height) + 1 ;
        return new info(nodes,height);
    }

判断一棵树是否是满二叉树

剑指 Offer 55 - I. 二叉树的深度

1
2
3
4
5
  3
 / \
9  20       返回它的最大深度 3
  /  \
 15   7

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
public int maxDepth(TreeNode root) {

       if(root == null){
           return 0;
       }

       int leftHeight = maxDepth(root.left);
       int rightHeight = maxDepth(root.right);

       int height = Math.max(leftHeight,rightHeight) + 1;

       return height;
   }
  • 轻松拿下

    判断一棵树是否是满二叉树

    题解

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    // 判断满二叉树
    public boolean isFullTree(TreeNode root){
        info res = process(root);
        return res.nodes == (Math.pow(2,res.height) - 1);
    }

    private  class info{
        private int height; // 树的高度
        private int nodes; // 树节点个数

        info(int n, int h){
            this.height = h;
            this.nodes = n;
        }
    }

    //树形DP模板
    private info process(TreeNode head ){

        if(head == null){
            return new info(0,0);
        }
        // 左子树收集信息
        info leftData = isFullTree(head.left);
        // 右子树收集信息
        info rightData = isFullTree(head.right);

        // 跟新信息
        int nodes = leftData.nodes + rightData.nodes  + 1;
        int height = Math.max(leftData.height,rightData.height) + 1 ;
        return new info(nodes,height);
    }

    判断一棵树是否是平衡二叉树

  • 剑指 Offer 55 - II. 平衡二叉树
    1
    2
    3
    4
    5
      3
     / \
    9  20      返回 true
      /  \
     15   7

    题解

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    class Solution {
        public boolean isBalanced(TreeNode root) {
            return process(root).isBalan;
        }
        // 需要的信息
        public class info{
          boolean isBalan;
            int height;
            info(boolean i , int h){
                isBalan = i;
                height = h;
            }
        }

        public info process(TreeNode root){
            if(root == null){
                return new info(true,0);
            }

            info leftData = process(root.left);
            info rightData = process(root.right);

            // 获取当前节点的左子树和右子树的深度，并取最大值 
            int height = Math.max(leftData.height ,rightData.height) + 1;
            // 判断左右子树是不是平衡树，并判断左右深度是否小于2
            boolean isBalan =  leftData.isBalan && rightData.isBalan 
                                && Math.abs(leftData.height - rightData.height) < 2;

            return new info(isBalan,height);
        }

    }

    判断一棵树是否是搜索二叉树

  • leetcode 98. 验证二叉搜索树
1
2
3
4
5
  5
 / \
1  4      返回 false
  /  \
 3    6

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
    
    public boolean isValidBST(TreeNode root) {
        return process(root).isBst;
    }

    public class info{
        public boolean isBst;
        public int max;
        public int min;
        info(boolean i,int min,int max){
            this.isBst = i;
            this.min = min;
            this.max = max;
        }
    }

    public info process(TreeNode head){

        if(head == null){
            return null;
        }

        info leftData = process(head.left);
        info rightData = process(head.right);
        int max = head.val;
        int min = head.val;
        if(leftData != null){
            min = Math.min(leftData.min,min);
            max = Math.max(leftData.max,max); 
        }
        if(rightData != null){
            min = Math.min(rightData.min,min);
            max = Math.max(rightData.max,max);
        }

        boolean isbst = true;
        if(leftData != null && (!leftData.isBst || leftData.max >= head.val) ){
            isbst = false;
        }
        if(rightData != null && (!rightData.isBst || rightData.min <= head.val) ){
            isbst = false;
        }

        return new info(isbst,min,max);
    }
}

进阶练习

  • leetcode 236. 二叉树的最近公共祖先
    1
    2
    3
    4
    5
      3
     / \
    5   1      p = 1,q =6 返回节点1和节点6的最近公共祖先是1
       /  \
      3    6

    题解

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    class Solution {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            // 找到q和p节点返回
            // 如果有一个节点在另一个节点下方则为空
            if(root == null || root == p || root == q ){
                return root;
            }
            // 左右子树收集节点
            TreeNode left = lowestCommonAncestor(root.left,p,q);
            TreeNode right = lowestCommonAncestor(root.right,p,q);

            // 判断是否找到了两个节点 如果到找到了则当前节点为最近公共祖先 
            if(left != null && right != null){
                return root;
            }
            // 判断哪个节点没有找到，则说明下个节点在当前节点的下方，
            // 即当前节点为最近公共祖先
            return left != null ?  left : right;
        }
    }