Question

求二叉樹的最大深度

Given a binary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

二叉樹的定義

 // Definition for a binary tree node.
 public class TreeNode {
     int val;
     TreeNode left;
     TreeNode right;
     TreeNode(int x) { val = x; }
 }

Solutions

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

一開始忘記max函數(shù)怎么用，就寫成了這樣

if (left > right) {
            return left + 1;
        } else {
            return right + 1;
        }

One Line Show

return (root == null) ? 0 : Math.max(maxDepth(root.left) + 1, maxDepth(root.right) + 1);

Points

• 二叉樹的數(shù)組表現(xiàn)
  [1,null,2,3]這樣的數(shù)組，順序?yàn)閺纳贤旅啃兄械膹淖蟮接业墓?jié)點(diǎn)。
  null表示空節(jié)點(diǎn)。[]表示空樹。
  array[i]的左子樹為array[i*2]，右子樹為array[i*2+1]。

  BinaryTree.png

• 節(jié)點(diǎn)為null的處理

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

• 遞歸的效率
  當(dāng)一個(gè)函數(shù)用它自己來定義時(shí)，就稱為遞歸（recursive）的；

  紗布如我一開始是這樣寫的

if (maxDepth(root.left) >= maxDepth(root.right)) {
     return maxDepth(root.left) + 1;
 } else {
     return maxDepth(root.right) + 1;
}

多么直觀，然后就感人的Time Limit Exceeded了。
這里大概是因?yàn)槊看握{(diào)用一次maxDepth都進(jìn)行了一次遞歸，所以應(yīng)該把maxDepth的結(jié)果保存成值再進(jìn)行比較和返回。
這樣寫就沒問題了

int left = maxDepth(root.left);
int right = maxDepth(root.right);
      
if (left > right) {
      return left + 1;
} else {
      return right + 1;
}

然后再精簡(jiǎn)點(diǎn)

return Math.max(maxDepth(root.right), maxDepth(root.left)) + 1;

TO DO

• 二叉樹相關(guān)概念
• Math.max 源碼分析