Monday, November 10, 2014

[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时。

1 comment:

  1. I have read your blog its very attractive and impressive. I like it your blog.
    Splitwise
    appvn

    ReplyDelete