面试题34:二叉树中和为某一数值的路径

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

整体思路如书上一致,但是要特特别别强调一点的是:容器vector作为函数参数传参的问题:要么引用传递,要么指针传递,尽量都采用引用传递。

例如这个代码中:

void findSinglePath(TreeNode* tNode,int expectNumber,int currentSum,vector<int> &singlePath,vector<vector<int> > &allPath)
这一句函数代码声明,不能漏掉那两个表示引用传递的&符号

整体代码:

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) {
        vector<vector<int> > allPath;
        if(root==nullptr)
            return allPath;
        vector<int> singlePath;
        int currentSum=0;
        findSinglePath(root,expectNumber,currentSum,singlePath,allPath);
        return allPath;
    }

    //递归根的左子树或右子树,寻找满足条件的路径节点
    void findSinglePath(TreeNode* tNode,int expectNumber,int currentSum,vector<int> &singlePath,vector<vector<int> > &allPath)
    {
        currentSum+=tNode->val;
        singlePath.push_back(tNode->val);
        //退出递归条件:若某点值等于剩余值,说明这是一条完整的路径;若找到叶子结点剩余值仍不等于当前叶子结点值,则放弃这条路径。
        if(expectNumber==currentSum&&tNode->left==nullptr&&tNode->right==nullptr)
            allPath.push_back(singlePath);

        //若不是叶子结点,则遍历它的左右子节点
        if(tNode->left)
            findSinglePath(tNode->left,expectNumber,currentSum,singlePath,allPath);
        if(tNode->right)
            findSinglePath(tNode->right,expectNumber,currentSum,singlePath,allPath);
        //代码走到这里,表示要回溯了,代表当前path的root节点已经不需要了
        if(singlePath.size()!=0)
            singlePath.pop_back();
    }
};
全部评论

相关推荐

10-27 17:26
东北大学 Java
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务