题解 | #二叉树中和为某一值的路径(一)#

题目的主要信息：

• 给定一个二叉树root和一个值 sum ，判断是否有从根节点到叶子节点的节点值之和等于 sum 的路径
• 路径定义为从树的根节点开始往下一直到叶子节点所经过的节点
• 路径只能从父节点到子节点，不能从子节点到父节点

举一反三：

学习完本题的思路你可以解决如下题目：

BM28. 二叉树的最大深度

BM29. 二叉树中和为某一值的路径（一）

BM31. 对称的二叉树

BM32. 合并二叉树

BM33. 二叉树的镜像

BM36. 判断是不是平衡二叉树

BM39. 序列化二叉树

BM41. 输出二叉树的右视图

方法一：递归（推荐使用）

知识点：二叉树递归

递归是一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。因此递归过程，最重要的就是查看能不能讲原本的问题分解为更小的子问题，这是使用递归的关键。

而二叉树的递归，则是将某个节点的左子树、右子树看成一颗完整的树，那么对于子树的访问或者操作就是对于原树的访问或者操作的子问题，因此可以自我调用函数不断进入子树。

思路：

既然是检查从根到叶子有没有一条等于目标值的路径，那肯定需要从根节点遍历到叶子，我们可以在根节点每次往下一层的时候，将sum减去节点值，最后检查是否完整等于0. 而遍历的方法我们可以选取二叉树常用的递归前序遍历，因为每次进入一个子节点，更新sum值以后，相当于对子树查找有没有等于新目标值的路径，因此这就是子问题，递归的三段式为：

• 终止条件： 每当遇到节点为空，意味着过了叶子节点，返回。每当检查到某个节点没有子节点，它就是叶子节点，此时sum减去叶子节点值刚好为0，说明找到了路径。
• 返回值： 将子问题中是否有符合新目标值的路径层层往上返回。
• 本级任务： 每一级需要检查是否到了叶子节点，如果没有则递归地进入子节点，同时更新sum值减掉本层的节点值。

具体做法：

• step 1：每次检查遍历到的节点是否为空节点，空节点就没有路径。
• step 2：再检查遍历到是否为叶子节点，且当前sum值等于节点值，说明可以刚好找到。
• step 3：检查左右子节点是否可以有完成路径的，如果任意一条路径可以都返回true，因此这里选用两个子节点递归的或。

Java实现代码：

import java.util.*;
public class Solution {
    public boolean hasPathSum (TreeNode root, int sum) {
        //空节点找不到路径
        if(root == null) 
            return false;
        //叶子节点，且路径和为sum
        if(root.left == null && root.right == null && sum - root.val == 0) 
            return true;
        //递归进入子节点
        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val); 
    }
}

C++实现代码：

class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum) {
        //空节点找不到路径
        if(root == NULL) 
            return false;
        //叶子节点，且路径和为sum
        if(root->left == NULL && root->right == NULL && sum - root->val == 0) 
            return true;
        //递归进入子节点
        return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val);
    }
};

Python实现代码

class Solution:
    def hasPathSum(self , root: TreeNode, sum: int) -> bool:
        # 空节点找不到路径
        if not root: 
            return False
        # 叶子节点，且路径和为sum
        if not root.left and not root.right and sum - root.val == 0:
            return True
        # 递归进入子节点
        return self.hasPathSum(root.left, sum - root.val) or self.hasPathSum(root.right, sum - root.val)

复杂度分析：

• 时间复杂度：$O(n)O(n)$，其中$nn$为二叉树所有节点，前序遍历二叉树所有节点
• 空间复杂度：$O(n)O(n)$，最坏情况二叉树化为链表，递归栈空间最大为$nn$

方法二：非递归（扩展思路）

知识点1：栈 栈是一种仅支持在表尾进行插入和删除操作的线性表，这一端被称为栈顶，另一端被称为栈底。元素入栈指的是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；元素出栈指的是从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

知识点2：深度优先搜索（dfs）

深度优先搜索一般用于树或者图的遍历，其他有分支的（如二维矩阵）也适用。它的原理是从初始点开始，一直沿着同一个分支遍历，直到该分支结束，然后回溯到上一级继续沿着一个分支走到底，如此往复，直到所有的节点都有被访问到。

思路：

在二叉树中能够用递归解决的问题，很多时候我们也可以用非递归来解决。这里遍历过程也可以使用栈辅助，进行dfs（深度优先搜索）遍历，检查往下的路径中是否有等于sum的路径和。

注意，这里仅是dfs，而不是前序遍历，左右节点的顺序没有关系，因为每次往下都是单独添加某个节点的值相加然后继续往下，因此左右节点谁先遍历不管用。

具体做法：

• step 1：首先检查空节点，空树没有路径。
• step 2：使用两个栈同步遍历，一个栈记录节点，辅助深度优先搜索，另一个栈跟随记录到该节点为止的路径和（C++中可以在一个栈中嵌套pair实现）。根节点及根节点值先进栈。
• step 3：遍历的时候每次弹出两个栈中的内容，判断是否是叶子节点且路径和是否等于目标值。
• step 4：没有到叶子节点就将左右子节点（如果有）加入栈中，并跟随加入路径和。
• step 5：如果遍历结束也没有找到路径和，则该二叉树中没有。

图示：

Java实现代码：

import java.util.*;
public class Solution {
    public boolean hasPathSum (TreeNode root, int sum) {
        //空节点找不到路径
        if(root == null) 
            return false;
        //栈辅助深度优先遍历
        Stack<TreeNode> s1 = new Stack<TreeNode>(); 
        //跟随s1记录到相应节点为止的路径和
        Stack<Integer> s2 = new Stack<Integer>(); 
        s1.push(root);
        s2.push(root.val);
        while(!s1.isEmpty()){
            //弹出相应节点
            TreeNode temp = s1.pop(); 
            //弹出到该点为止的当前路径和
            int cur_sum = s2.pop(); 
            //叶子节点且当前路径和等于sum
            if(temp.left == null && temp.right == null && cur_sum == sum)
                return true;
            //左节点及路径和入栈
            if(temp.left != null){ 
                s1.push(temp.left);
                s2.push(cur_sum + temp.left.val);
            }
            //右节点及路径和入栈
            if(temp.right != null){ 
                s1.push(temp.right);
                s2.push(cur_sum + temp.right.val);
            }
        }
        return false;
    }
}

C++实现代码：

class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum) {
        //空节点找不到路径
        if(root == NULL) 
            return false;
        //栈辅助深度优先遍历，并记录到相应节点的路径和
        stack<pair<TreeNode*, int> > s; 
        //根节点入栈
        s.push({root, root->val}); 
        while(!s.empty()){
            auto temp = s.top();
            s.pop();
            //叶子节点且路径和等于sum
            if(temp.first->left == NULL && temp.first->right == NULL && temp.second == sum)
                return true;
            //左节点入栈
            if(temp.first->left != NULL) 
                s.push({temp.first->left, temp.second + temp.first->left->val});
            //右节点入栈
            if(temp.first->right != NULL) 
                s.push({temp.first->right, temp.second + temp.first->right->val});
        }
        return false;
    }
};

Python实现代码

class Solution:
    def hasPathSum(self , root: TreeNode, sum: int) -> bool:
        # 空节点找不到路径
        if not root: 
            return False
        # 栈辅助深度优先遍历，并记录到相应节点的路径和
        s = [] 
        # 根节点入栈
        s.append((root, root.val)) 
        while len(s):
            temp = s[-1]
            s.pop()
            # 叶子节点且路径和等于sum
            if (not temp[0].left) and (not temp[0].right) and (temp[1] == sum):
                return True
            # 左节点入栈
            if temp[0].left: 
                s.append((temp[0].left, temp[1] + temp[0].left.val))
            # 右节点入栈
            if temp[0].right: 
                s.append((temp[0].right, temp[1] + temp[0].right.val))
        return False

复杂度分析：

• 时间复杂度：$O(n)O(n)$，其中$nn$为二叉树所有节点，遍历二叉树所有节点
• 空间复杂度：$O(n)O(n)$，最坏情况二叉树化为链表，递归栈空间最大为$nn$