剑指offer 34 二叉树和为某一值的路径 C++

剑指offer 34 二叉树和为某一值的路径

• 二叉树搜索路径问题-递归回溯
• • 1. DFS回溯 (显式)
  • 2. DFS回溯（隐式）
  • 3. 类似搜索路径题目

二叉树搜索路径问题-递归回溯

题目链接

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

将求路径节点和转化为差，target不断减去节点val, 到达叶节点后值为0，则满足条件。

1. DFS回溯 (显式)

class Solution {
public:
	vector> res;
	vector path;
	
	void dfs(TreeNode* root, int target) {
		if (!root) return; // 越过叶节点，终止递归
		path.push_back(root->val);
		target -= root->val;
		
		// 遇见叶节点且目标减到 0
		if (root->left == NULL && root->right == NULL && target == 0) {
			res.push_back(path);
		}
		dfs(root->left, target);
		dfs(root->right, target);
		path.pop_back();  // 回溯d出之前路径的节点
	}

	vector> pathSum(TreeNode* root, int target) {
        dfs(root, target);
        return res;
    }
};

时间、空间复杂度：O(n) ，n 为节点数。

二叉树图片来自Leetcode题目描述

• 遍历完一条路径后，需要将路径中之前路径的节点d出才能加入新路径的节点。
• 以上图中第一条路径 5-4-11-7 为例:
  • 递归到叶节点 7 后，7被加入path, 并进行判断：路径和不等于目标值, 不加入结果。
  • 7 左右节点皆为NULL, 终止遍历，然后路径中d出 7。
  • 7节点为父节点 11 的左节点，递归7结束后，再递归11 的右节点 2
• 每次子节点验证完 path，返回上一层，都会把这一层的节点值从 path 中d出，即回溯。

2. DFS回溯（隐式）

class Solution {
public:
    vector> res;
    
    void helper(TreeNode* root, vector path, int target) {
        path.push_back(root->val);
        target -= root->val;
        if (!root->left && !root->right) {
            if (target == 0) res.push_back(path);
            return;
        }
        if (root->left) helper(root->left, path, target);
        if (root->right) helper(root->right, path, target);
    }
    
    vector> pathSum(TreeNode* root, int target) {
        if (!root) return {};
        helper(root, {}, target);
        return res;
    }
};

• 辅助函数 path 变量是通过按值传参（复制），不是按引用传参。
• 递归下一节点改变的是下一层的局部变量，本层的 path 值不变，因此不需要pop_back().

3. 类似搜索路径题目

二叉树的所有路径

class Solution {
public:
    vector res; 
    void dfs(TreeNode* root, string path) {
        path += to_string(root->val);
        if (root->left == NULL && root->right == NULL) {
            res.push_back(path);
            return;
        }
        if (root->left) dfs(root->left, path + "->");
        if (root->right) dfs(root->right, path + "->");
    }

    vector binaryTreePaths(TreeNode* root) {
        if (!root) return res;
        dfs(root, "");
        return res;
    }
};