二叉树中和为某一值的路径

题目描述

输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)

解题思路：

看到树的题目99%的可能就想递归的方法

在这道题目中，树的路径被定义为：从树的根结点开始往下一直到叶结点所经过的结点形成一条路径

所以，借助一个辅助栈，从根结点开始，将根结点压入到栈中

然后判断这个结点是不是叶子结点

若不是叶子结点，则递归向其左右孩子继续调用该函数

若是叶子结点，则继续判断这个结点所在的路径之和是否满足题目的要求，如果满足则保留答案

结点为叶子结点也作为递归退出的条件

代码：

class Solution {
public:
    vector<vector<int> > FindPath(TreeNode *root, int expectNumber) {
        find(root, expectNumber);
        return result;
    }

    void find(TreeNode *root, int expectNumber) {
        if (root == NULL) 
            return;

        int sum = 0;
        path.push_back(root->val);
        sum += root->val;

        bool isLeaf = !(root->left || root->right);
        // 如果该结点是叶子结点，且路径之和等于要求
        // 则记录此答案
        if (isLeaf && sum == expectNumber) {
            result.push_back(path);
        }
        // 如果不满足则因为两种情况
        else {
            // 1.不是叶子节点，所以继续下探
            if (root->left != NULL) {
                find(root->left, expectNumber - (root->val));
            }

            if (root->right != NULL) {
                find(root->right, expectNumber - (root->val));
            }
        }
        // 2.与题目所要求的和不相等，弹出尾部元素（叶节点)
        path.pop_back();
    }

private:
    vector<vector<int> > result;
    vector<int> path; 
};

2018.10.16