[LeetCode] Minimum/Maximum Depth of Binary Tree

Given a binary tree, find its minimum/maximum depth.

The minimum/maximum depth is the number of nodes along the shortest/longest path from the root node down to the nearest/farthest leaf node.

思考：

Leetcode有这样一大类binary tree的题目，需要遍历查找从root到leaf的path，从而求得一个和path相关的值。而最直观的思路就是用top-down递归来进行访问。

1. 递归访问的时候从上一层传递所关心的path变量（例如这两题中的当前节点的depth以及当前的min/max depth）到下一层（即当前节点的left/right children）。

2. 在每一中间层中对这个传递变量进行更新修改：每一层增加当前的depth。

3. 终止条件：直到访问到某个leaf节点时，一条path找到，不再进行更深层的递归，而是进行所需要的更新操作：更新min/max depth的值。

Minimum depth of binary tree:

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

class Solution { public: int minDepth(TreeNode *root) { int minDpt = INT_MAX; searchMinPath(root, 0, minDpt); return minDpt; } void searchMinPath(TreeNode *root, int curDpt, int &minDpt) { if(!root) { minDpt = 0; return; } curDpt++; if(!root->left && !root->right) { // reach a leaf node minDpt = min(minDpt,curDpt); return; } if(root->left) searchMinPath(root->left,curDpt,minDpt); if(root->right) searchMinPath(root->right,curDpt,minDpt); } };

Maximum depth of binary tree:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

class Solution { public: int maxDepth(TreeNode *root) { int maxDpt = 0; searchMaxPath(root, 0, maxDpt); return maxDpt; } void searchMaxPath(TreeNode *root, int curDpt, int &maxDpt) { if(!root) { maxDpt = 0; return; } curDpt++; if(!root->left && !root->right) { maxDpt = max(curDpt,maxDpt); return; } if(root->left) searchMaxPath(root->left, curDpt, maxDpt); if(root->right) searchMaxPath(root->right, curDpt, maxDpt); } };

总结： 简单题，但要注意几个细节：

(1) 起始值：minDpt = INT_Max, maxDpt = 0.

(2) 当root为NULL时。

(3) 当root只有一个child时。