喜刷刷: recursion

Showing posts with label recursion. Show all posts

Monday, November 10, 2014

[LeetCode] Validate Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
Both the left and right subtrees must also be binary search trees.

解法1：min/max法

这是我觉得最直接了当、简洁易懂的方法：

1. 先top-down递归，由父节点来传递子节点的值所允许的范围minVal < x->val < maxVal。如果该条件不符合，返回false。

2. 如果上述条件符合，只说明当前节点x本身符合BST条件。还需要bottom-up递归来检查当前节点的左右子树是否也都符合BST条件。左子树的取值范围为(minVal, x->val)，右子树取值范围为(x->val, maxVal)。

class Solution {
public:
    bool isValidBST(TreeNode *root) {
        return validateBST(root, INT_MIN, INT_MAX);
    }
    
    bool validateBST(TreeNode *root, int minVal, int maxVal) {
        if(!root) return true;
        if(root->val<=minVal || root->val>=maxVal) return false;
        return validateBST(root->left, minVal, root->val) && validateBST(root->right, root->val, maxVal);
    }
};

解法2：inorder traversal法
1. 对一个BST进行inorder traverse，必然会得到一个严格单调递增序列，否则则是invalid BST。

2. Inorder traverse时并不需要记录下整个访问过的序列，而只需要保存前一个访问的节点数值就可以了。

class Solution {
public:
    bool isValidBST(TreeNode *root) {
        int curMax = INT_MIN;
        return validateBST(root, curMax);
    }
    
    bool validateBST(TreeNode *root, int &curMax) {
        if(!root) return true;
        if(!validateBST(root->left, curMax)) return false;
        if(curMax >= root->val) return false;
        curMax = root->val;
        return validateBST(root->right, curMax);
    }
};

ln 10:检验左子树是否valid，并通过引用得到左子树的最大值curMax。

ln 11-12:在左子树valid的情况下，判断当前节点是否大于curMax。在当前节点也valid的情况下，更新curMax为当前节点。

ln 13:当左子树和当前节点都valid时，返回右子树的检验结果即可。

[LeetCode] Balanced Binary Tree

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

思路：

1. Tree depth的定义：为当前节点左右subtree depth中的较大值加1.

depth(root) = max[ depth(root->left), depth(root->right) ] + 1

而对NULL节点的depth在有的书上定义为-1，有的书上定义为0。但这个定义并不影响对balance binary tree的判断，所以这里假设NULL节点的depth为0，即leaf节点的depth为1.

2. 如何判断balance？

(1). 一个binary tree中有任何一个subtree不平衡，那么整个tree不平衡。

(2) 当x->left和x->right的subtree都平衡时，只有abs(depth(x->left) - depth(x->right))<=1时，以x的subtree才平衡。

3. 如何递归？

Bottom-up递归，因为只有当某一节点左右子树的depth以及左右子树是否平衡都得知以后，才能判断该节点为根的树是否平衡，以及求得该节点的depth。

Base case: NULL节点depth返回0。

4. 函数返回什么？

函数即要返回当前节点为根的树的depth，以便于父节点判断平衡和计算depth。同时也需要返回该树是否平衡的判断。可以将两个返回值合并在一起：由于最小的depth为0（NULL节点），在返回depth时可以以 -1 来表示该子树不平衡。

class Solution {
public:
    bool isBalanced(TreeNode *root) {
        return findDepth(root)==-1 ? false : true;
    }
    
    int findDepth(TreeNode *root) {
        if(!root) return 0;
        
        int leftDepth = findDepth(root->left);      // left subtree depth
        if(leftDepth==-1) return -1;
        
        int rightDepth = findDepth(root->right);    // right subtree depth
        if(rightDepth==-1) return -1;
        
        if(abs(leftDepth-rightDepth)>1) return -1;
        
        return max(leftDepth,rightDepth)+1;
    }
};

总结：

代码中ln 11之所以不和ln 14合并放在ln 13之后，是因为当左子树不平衡时，没有必要再对右子树求depth，直接返回-1即可。这类代码中的剪枝优化需要经常注意。

[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] Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

For example:
Given the below binary tree,

       1
      / \
     2   3

Return 6.

思路：
1. 与常规path sum不同，这题的path sum可以不起始于root，也可以不终止于leaf。

2. 这样的path可以归纳为两种情况：
(1) root->leaf path中的一段：即题目例子中的1-2或1-3。
(2) 两个节点之间经过它们lowest common ancestor (LCA)的path：即题目中的2-1-3。

3. 显然top-down的递归并不适用于这题，因为对于类型(2)的path，它的path sum同时取决于LCA左右sub path的最大值。而这样的path sum是无法通过top-down传递来获取的。

4. 所以这里可以采用bottom-up的递归方法:
对于节点x:
定义PS1(x)为从x出发向leaf方向的第一类path中最大的path sum。
定义PS2(x)为以x为LCA的第二类path中的最大path sum。
显然如果我们求得所有节点x的PS1 & PS2，其中的最大值必然就是要求的max path sum。

5. 如何求PS1(x)、PS2(x)?
(1) PS1(x) 、PS2(x)至少应该不小于x->val，因为x自己就可以作为一个单节点path。
(2) PS1(x) 、 PS2(x)可以从PS1(x->left)和PS1(x->right)来求得：
PS1(x) = max [ max(PS1(x->left), 0), max(PS1(x->right), 0) ] + x->val
PS2(x) = max(PS1(x->left), 0) + max(PS1(x->right), 0) + x->val
注意这里并不需要PS2(x->left) 以及 PS2(x->right) 因为子节点的2型path无法和父节点构成新的path。

6. 需要返回PS1(x)以供上层的节点计算其PS1 & PS2.

7. 对于leaf节点：PS1(x) = PS2(x) = x->val.

class Solution {
public:
    int maxPathSum(TreeNode *root) {
        int maxSum = INT_MIN;
        int ps1_root = findMaxPathSum(root, maxSum);
        return maxSum;
    }
    
    int findMaxPathSum(TreeNode *root, int &maxSum) {
        if(!root) return 0;
        
        int ps1_left = 0, ps1_right = 0;
        if(root->left) 
            ps1_left = max(findMaxPathSum(root->left,maxSum),0);
        if(root->right)
            ps1_right = max(findMaxPathSum(root->right,maxSum),0);
        
        int ps1_root = max(ps1_left, ps1_right) + root->val;    
        int ps2_root = ps1_left + ps1_right + root->val;
        maxSum = max(maxSum,max(ps1_root, ps2_root));
        
        return ps1_root;
    }
};

总结：

1. 解题的关键在于对path的分类以及应用top-down recursion。

2. 注意的细节是当x->left或x->right的第一类path sum为负数时，则这类path不应该传递到x：ln 13-16。

3. 代码并没有特殊处理leaf节点的情况。因为当root->left和root->right都不存在时，ps1_left和ps1_right均为初始值0：ln 12。于是ps1_root = ps2_root = root->val。

[LeetCode] Path Sum I, II

Path Sum I

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example:
Given the below binary tree and sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

Path Sum II

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

For example:
Given the below binary tree and sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1

return

[
   [5,4,11,2],
   [5,8,4,5]
]

思路：

1. 和min/max depth那两题类似，同样属于binary tree root->leaf path类的题目。思路也是递归，直到找到leaf为止。

2. 传递的path变量：

(1) 可以是当前path上已经访问过的所有节点的sum。这样到leaf时判断是否与目标sum相等。

(2) 也可以是目标sum减去当前path上已经访问的所有节点的sum。这样到leaf时，只要判断leaf节点的值是否等于传递下来的剩余sum即可。

Path Sum I

class Solution {
public:
    bool hasPathSum(TreeNode *root, int sum) {
        if(!root) return false;
        
        sum -= root->val;
        if(!root->left && !root->right) 
            return sum==0 ? true : false;
            
        if(root->left && hasPathSum(root->left,sum)) return true;
        if(root->right && hasPathSum(root->right,sum)) return true;
        return false;
    }
};

Path Sum II

class Solution {
public:
    vector<vector<int> > pathSum(TreeNode *root, int sum) {
        vector<int> path;
        vector<vector<int> > allPaths;
        finaPathSum(root, sum, path, allPaths);
        return allPaths;
    }
    
    void finaPathSum(TreeNode *root, int sum, vector<int> &path, vector<vector<int> > &allPaths) {
        if(!root) return;
        sum -= root->val;
        path.push_back(root->val);
        
        if(!root->left && !root->right) {
            if(sum==0) {
                allPaths.push_back(path);
            }
        }
        else {
            if(root->left) finaPathSum(root->left, sum, path, allPaths);
            if(root->right) finaPathSum(root->right, sum, path, allPaths);
        }
        
        path.pop_back();
    }
};

总结：

1. Path Sum I和II的思路基本是一样的。区别在于I只需要任意找到一条符合条件的path，就可结束查找。所以ln 10 & 11只需要在左或右子树中找到了一条path，就可以return true将结果传递回去。而对于II来说，由于需要找到所有符合条件的path，ln 21 & 22则必须同时搜索左右子树。

2. Path Sum II要求返回所有路径的集合。这也是很常见的一种函数返回类型要求。通常的做法是用一个一维vector变量存储当前解(path)，用一个二维vector存储最终的解集合(allPaths)。每层递归不断更新当前解，直到递归结束找到解后更新解集合。

3. Path Sum II中要注意ln 25对path的reset。无论递归是否结束，或者解是否找到，都不能在返回前遗漏这一步reset。因为通过当前节点的所有path已经都访问到了，返回前需要从path中删除当前节点，以便重新构建其他path。

4. 这类int求和问题都可能存在overflow的问题。需要和面试官交流明确是否程序中要检查。

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