喜刷刷: path

Monday, November 10, 2014

[LeetCode] Sum Root to Leaf Numbers

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

For example,

    1
   / \
  2   3

The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.

Return the sum = 12 + 13 = 25.

思路：

典型的root->leaf path问题，遍历所有path并更新sum。传递的变量是当前节点的path num值curNum。则下一层的节点对应的path num为curNum*10 + val。

class Solution {
public:
    int sumNumbers(TreeNode *root) {
        int sum = 0;
        sumRootToLeafNum(root, 0, sum);
        return sum;
    }
    
    void sumRootToLeafNum(TreeNode *root, int curNum, int &sum) {
        if(!root) return;
        curNum = curNum*10 + root->val;
        if(!root->left && !root->right) sum += curNum;
        if(root->left) sumRootToLeafNum(root->left, curNum, sum);
        if(root->right) sumRootToLeafNum(root->right, curNum, sum);
    }
};

总结：

当root->leaf path很长时，path num将会很大，sum的时候很容易出现溢出。需要和面试官讨论是否要特殊处理这样的情况。另外当root为NULL时需要返回0.

[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:

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:

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