三个经典例题

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

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

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

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

模板

定义一个返回信息

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;
    }
    }