【剑指Offer】二叉树的深度

Posted on | In ,

题目一

输入一棵二叉树的根结点，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。

实现

1
2
3
4
5
6
7
8
9
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
 
    public TreeNode(int val) {
        this.val = val;
    }
}
1
2
3
4
5
6
7
8
9
public int TreeDepth(TreeNode root) {
    if (root == null)
        return 0;

    int leftDepth = TreeDepth(root.left);
    int rightDepth = TreeDepth(root.right);

    return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}

题目二

输入一棵二叉树的根结点，判断该树是不是平衡二叉树。如果某二叉树中任意结点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。

需要重复遍历结点多次的解法，简单但不足以打动面试官

1
2
3
4
5
6
7
8
9
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
 
    public TreeNode(int val) {
        this.val = val;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public boolean IsBalanced_Solution(TreeNode root) {
    if (root == null)
        return true;

    int leftDep = TreeDepth(root.left);
    int rightDep = TreeDepth(root.right);

    return IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right) && Math.abs(leftDep - rightDep) < 2;
}

private int TreeDepth(TreeNode root) {
    if (root == null)
        return 0;

    int leftDepth = TreeDepth(root.left);
    int rightDepth = TreeDepth(root.right);

    return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}

每个结点只遍历一次的解法，正是面试官喜欢的

1
2
3
4
5
6
7
8
9
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
 
    public TreeNode(int val) {
        this.val = val;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
private boolean isBalanced = true;

public boolean IsBalanced_Solution(TreeNode root) {
    getDepth(root);
    return isBalanced;
}

private int getDepth(TreeNode root) {
    if (root == null)
        return 0;

    int leftDep = getDepth(root.left);
    int rightDep = getDepth(root.right);

    if (Math.abs(leftDep - rightDep) > 1)
        isBalanced = false;

    return Math.max(leftDep, rightDep) + 1;
}