【剑指Offer】T34 二叉树中和为某一值的路径

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

思路:利用先序遍历进行探路

  • 访问节点,添加到路径内,计算累加值
  • 如果是叶节点
    • 累加值符合要求:打印
    • 不符合要求,删最后的叶节点,访问 父节点的另外一个孩子,不符合的话继续回溯
  • 借助栈来实现(题目给的是 vector,pop_back 是最后一个元素,可以代替栈)
class Solution {
public:
    int num;
    vector<int> path;
    vector<vector<int> > res;
    void finder(TreeNode* root, int expectNumber){
        // 空,递归出口
        if(!root)
            return;
        
        num += root->val;
        path.push_back(root->val);
        
        // 符合条件,路径存入
        if(!root->left && !root->right && num==expectNumber)
            res.push_back(path);
        
        //继续探路
        finder(root->left, expectNumber);
        finder(root->right, expectNumber);
        // 探到叶节点,回溯
        path.pop_back();
        num-=root->val;
    }
    vector<vector<int> > FindPath(TreeNode* root, int expectNumber) {
        finder(root, expectNumber);
        return res;
    }
};

本文链接:https://ariser.cn/index.php/archives/384/
本站文章采用 知识共享署名4.0 国际许可协议进行许可,请在转载时注明出处及本声明!