《剑指Offer》二叉树中和为某一值的路径

题目描述：

  输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

如图，输入上图的二叉树和整数 22，则打印出两条路径，第一条路径：10, 12； 第二条路径为：10， 5， 7.

解题思路：

由于路径是从根节点出发到叶节点，也就是说路径总是以根节点为起始点，因此首先需要遍历根节点。在树的前序，中序，后序三种遍历方式中，只有前序遍历是首先访问根节点。

遍历过程如下表：

  深度优先搜索。使用前序遍历，使用两个全局变量result和tmp，result来存放最终结果，tmp用来存放临时结果。

  每次遍历，我们先把root的值压入tmp，然后判断当前root是否同时满足：
  - 与给定数值相减为0；
  - 左子树为空；
  - 右子树为空。

  如果满足条件，就将tmp压入result中，否则，依次遍历左右子树。需要注意的是，遍历左右子树的时候，全局变量tmp是不清空的，直到到了根结点才请空tmp。

代码实现(c++)

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
public:
    vector<vector<int> > findPath(TreeNode* root,int expectNumber){
        if(root == NULL){
            return result;
        }

        tmp.push_back(root->val);
        if((expectNumber - root->val ) == 0 && root->left == NULL && root->right == NULL){
            result.push_back(tmp);
        }

        //遍历左子树
        FindPath(root->left, expectNumber - root->val);
        //遍历右子树
        FindPath(root->right, expectNumber - root->val);

        tmp.pop_back();
        return result;
    }
private:
    vector<vector<int> > result;
    vector<int> tmp;
};

代码实现(python)

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    # 返回二维列表，内部每个列表表示找到的路径
    def FindPath(self, root, expectNumber):
        # write code here
        if not root:
            return []
        if not root.left and not root.right and expectNumber == root.val:
            return [[root.val]]
        res = []
        left = self.FindPath(root.left, expectNumber-root.val)
        right = self.FindPath(root.right, expectNumber-root.val)
        for i in left+right:
            res.append([root.val]+i)
        return res
if __name__=='__main__':
    A1 = TreeNode(1)
    A2 = TreeNode(2)
    A3 = TreeNode(3)
    A4 = TreeNode(4)
    A5 = TreeNode(5)
    A6 = TreeNode(6)

    A1.left=A2
    A1.right=A3
    A2.left=A4
    A2.right=A5
    A4.left=A6

    solution=Solution()
    ans=solution.FindPath(A1,8)
    print('ans=',ans)

代码实现(java)

import java.util.ArrayList;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    ArrayList<Integer> path = new ArrayList<>();
    ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();

    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
        if(root == null) 
            return list;

        //每访问到一个结点的时候，都把当前的结点添加到路径中去，并调整target的值
        path.add(root.val);
        target -= root.val;

        //已到叶节点并且和为target，则把当前路径添加到输出列表里
        //因为add添加的是引用，如果不new一个的话，最终list保存到的只是最后一个path
        if(target == 0 && root.left == null && root.right == null)
            list.add(new ArrayList<Integer>(path));

        //否则继续遍历
        FindPath(root.left, target);
        FindPath(root.right, target);

        //已到叶节点之后会跳过两个递归函数到这里，此时要把最后一个结点从路径中删除，才能返回上层结点
        path.remove(path.size()-1);
        return list;
    }
}