Binary Tree Path Sum (Ladder)

Description

Given a binary tree, find all paths that sum of the nodes in the path equals to a given number target. A valid path is from root node to any of the leaf nodes.

Example:
Given a binary tree, and target = 5:

     1
    / \
   2   4
  / \
 2   3

return

[
  [1, 2, 2],
  [1, 4]
]

Link

Lintcode_ladder

Method

1. x
2. x

Example

1. 1

   /**
   * Definition of TreeNode:
   * class TreeNode {
   * public:
   *     int val;
   *     TreeNode *left, *right;
   *     TreeNode(int val) {
   *         this->val = val;
   *         this->left = this->right = NULL;
   *     }
   * }
   */
   class Solution {
   public:
    /**
     * @param root the root of binary tree
     * @param target an integer
     * @return all valid paths
     */
    vector<vector<int>> binaryTreePathSum(TreeNode *root, int target) {
        // Write your code here
        vector<vector<int>> result;
        if (!root) {
            return result;
        }
        // find and record path, reuse path : transferring reference
        vector<int> path;
        helper(result, path, root, target);
        return result;
    }
    void helper(vector<vector<int>>& result, vector<int>& path, 
        TreeNode* root, int target 
    ) {
        // unvalid node
        if (!root) {
            return;
        }
        // leaf node 
        if (!root->left && !root->right && target == root->val) { 
            path.push_back(root->val);
            result.push_back(path);
            path.pop_back();
            return;
        } 
        // no left node, for left child
        if (root->left) {
            path.push_back(root->val);
            helper(result, path, root->left, target - root->val);
            path.pop_back();
        }
        // no right node, for right child
        if (root->right) {
            path.push_back(root->val);
            helper(result, path, root->right, target - root->val);
            path.pop_back();
        }
        // nothing needs to do
        return;
    }
   };
   

Similar problems

x

Tags

x