題目一：二叉樹的深度

輸入一棵二叉樹，求該樹的深度。從根結點到葉結點依次經(jīng)過的結點（含根、葉結點）形成樹的一條路徑，最長路徑的長度為樹的深度。

練習地址

https://www.nowcoder.com/practice/435fb86331474282a3499955f0a41e8b
https://leetcode-cn.com/problems/er-cha-shu-de-shen-du-lcof/

參考答案

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

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

復雜度分析

• 時間復雜度：O(n)。
• 空間復雜度：O(n)。

題目二：平衡二叉樹

輸入一棵二叉樹，判斷該二叉樹是否是平衡二叉樹。如果某二叉樹中任意節(jié)點的左、右子樹的深度相差不超過1，那么它就是一棵平衡二叉樹。

練習地址

https://www.nowcoder.com/practice/8b3b95850edb4115918ecebdf1b4d222
https://leetcode-cn.com/problems/ping-heng-er-cha-shu-lcof/

需要重復遍歷節(jié)點多次的解法，簡單但不足以打動面試官

public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        if (root == null) {
            return true;
        }
        if (Math.abs(TreeDepth(root.left) - TreeDepth(root.right)) > 1) {
            return false;
        }
        return IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);
    }
    
    public int TreeDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(TreeDepth(root.left), TreeDepth(root.right)) + 1;
    }
}

復雜度分析

• 時間復雜度：O(n^2)。
• 空間復雜度：O(n)。參考：
  平均時間復雜度：O(log1+log2+...+logn)=O(log(n!))=O(nlogn)

每個節(jié)點只遍歷一次的解法，正是面試官喜歡的

public class Solution {
    private int mDepth;
    
    public boolean IsBalanced_Solution(TreeNode root) {
        if (root == null) {
            mDepth = 0;
            return true;
        }
        if (!IsBalanced_Solution(root.left)) {
            return false;
        }
        int left = mDepth;
        if (!IsBalanced_Solution(root.right)) {
            return false;
        }
        int right = mDepth;
        int diff = left - right;
        if (diff <= 1 && diff >= -1) {
            mDepth = 1 + (left > right ? left : right);
            return true;
        } else {
            return false;
        }
    }
}

復雜度分析

• 時間復雜度：O(n)。
• 空間復雜度：O(n)。

??劍指Offer Java版目錄
??劍指Offer Java版專題