首页 > 试题广场 >

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

[编程题]二叉树中和为某一值的路径(一)
  • 热度指数:163461 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定一个二叉树root和一个值 sum ,判断是否有从根节点到叶子节点的节点值之和等于 sum 的路径。
1.该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点
2.叶子节点是指没有子节点的节点
3.路径只能从父节点到子节点,不能从子节点到父节点
4.总节点数目为n

例如:
给出如下的二叉树,

返回true,因为存在一条路径 的节点值之和为 22

数据范围:
1.树上的节点数满足
2.每 个节点的值都满足
要求:空间复杂度 ,时间复杂度
进阶:空间复杂度 ,时间复杂度
示例1

输入

{5,4,8,1,11,#,9,#,#,2,7},22

输出

true
示例2

输入

{1,2},0

输出

false
示例3

输入

{1,2},3

输出

true
示例4

输入

{},0

输出

false

说明:本题目包含复杂数据结构TreeNode,点此查看相关信息
public boolean hasPathSum (TreeNode root, int sum) {
        // write code here
       if(root == null) return false;
       if(root.left == null && root.right == null && root.val == sum) return true;
       return hasPathSum(root.left,sum - root.val) || hasPathSum(root.right,sum - root.val);
    }

发表于 2022-03-29 21:52:13 回复(0)
后序非递归实现
    public boolean hasPathSum (TreeNode root, int sum) {
        if (root == null) {
            return false;
        }
         // 采用非递归的后序遍历实现
        Stack<TreeNode> stack = new Stack();
         
        int curSum = 0;
        TreeNode cur = root;
        TreeNode pre = null;
        while(cur != null || !stack.isEmpty()) {
            while (cur != null) {
                curSum += cur.val;
                stack.push(cur);
                cur = cur.left;
            }
            
            if (!stack.isEmpty()) {
                cur = stack.pop();
                curSum -= cur.val;
                if (cur.right == null || pre == cur.right) {
                    
                    if (cur.left == null && cur.right == null && curSum + cur.val == sum) {
                        return true;
                    }
                    
                    pre = cur;
                    cur = null;
                } else {
                    curSum += cur.val;
                    stack.push(cur);
                    cur = cur.right;
                }
            }
        }
        return false;
    }


发表于 2022-02-13 21:55:27 回复(0)
    public boolean hasPathSum (TreeNode root, int sum) {
        if(root == null) return false;
        // write code here
        return dfs(root,0,sum);
    }
    public boolean dfs(TreeNode root,int prevSum,int sum){
        if(root == null){
            return false;
        }
        int tempSum = prevSum + root.val;
        if(root.left == null && root.right == null){
            return tempSum == sum;
        }else{
            return dfs(root.left,tempSum,sum) || dfs(root.right,tempSum,sum);
        }
    }

发表于 2022-01-13 23:03:35 回复(0)
    public boolean hasPathSum (TreeNode root, int sum) {
        // 判空
        if(root==null){
            return false;
        }
        // 判断左右子树同时为空的同时,刨除val值的sum是否为0,如果成立说明刚好在叶子结点找到和为指定值的路径
        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);
    }

发表于 2022-01-02 15:38:31 回复(0)
import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @param sum int整型 
     * @return bool布尔型
     */
    public boolean hasPathSum (TreeNode root, int sum) {
        // write code here
        if (root == null)
            return false;
        return dfs(root, sum);
    }
    
    // 二叉树的深度遍历
    public boolean dfs(TreeNode tempNode, int target) {
        if (tempNode == null)
            return false;
        target = target - tempNode.val;
        if (tempNode.left == null && tempNode.right == null && target == 0){
            return true;
        }
        return dfs(tempNode.left, target) || dfs(tempNode.right, target);
    }
}

发表于 2021-12-07 21:27:15 回复(0)
public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @param sum int整型 
     * @return bool布尔型
     */
     int s = 0;
    boolean res = false;

    public boolean hasPathSum(TreeNode root, int sum) {
        dfs(root, sum);
        return res;
    }

    public void dfs(TreeNode root, int sum) {
        if (root == null)
            return;
        s += root.val;
     if (s == sum&&root.left==null&&root.right == null) {
            res = true;
            return;
        }
        if (s !=sum) {
            dfs(root.left, sum);
            dfs(root.right, sum);
            s = s - root.val;
        }
    }
}

发表于 2021-12-03 15:46:54 回复(0)
import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @param sum int整型 
     * @return bool布尔型
     */
    public boolean hasPathSum (TreeNode root, int sum) {
        // write code here
        if(root==null){
            return false;
        }
        return dfs(root,sum);
    }
    public boolean dfs (TreeNode root, int sum){
        if(root==null) return false;
        sum-=root.val;
        if(sum==0&&root.left==null&&root.right==null){
            return true;
        }
        return dfs(root.left,sum)||dfs(root.right,sum);
    }
}

发表于 2021-11-30 21:31:53 回复(0)
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    //回溯法
    //做选择,进行下一步,撤销选择。
    bool res=false;
    bool hasPathSum(TreeNode *root, int sum) {
        if(root==NULL) return false;
        track(root,sum);
        return res;
    }
    void track(TreeNode *root, int &sum)
    {
        if(root==NULL) return ;
        if(root->left==NULL&&root->right==NULL)
        {
            if(sum==root->val)
            {
                res=true;
            }
        }
        
        if(root->left)
        {
            sum=sum-root->val;
            track(root->left,sum);
            sum=sum+root->val;
        }
        if(root->right)
        {
            sum=sum-root->val;
            track(root->right,sum);
            sum=sum+root->val;
        }
        
    }
};


编辑于 2020-04-21 15:47:37 回复(0)
class Solution {
public:
    bool hasPathSum(TreeNode *root, int sum) {
        if(!root)
        	return false;
        if(root->left == NULL && root->right == NULL && root->val == sum)
        	return true;
        return hasPathSum(root->left , sum - root->val) || hasPathSum(root->right , sum - root->val);   	
    }
};

发表于 2017-08-03 01:59:09 回复(0)
public class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) {
            return false;
        }
        else if (root.left == null && root.right == null && sum == root.val) {
            return true;
        }
        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
    }
}

发表于 2017-06-25 17:35:14 回复(0)
先序遍历。
    bool hasPathSum(TreeNode *root, int sum) {
        if (!root) return false;
        if (root->val==sum && !root->left && !root->right) return true;
        return hasPathSum(root->left,sum-root->val) 
            || hasPathSum(root->right,sum-root->val);
    }

发表于 2016-08-04 17:50:46 回复(0)
//递归求解,当root为空返回false,当到达叶子节点,并且和位sum返回true
//其他情况递归调用左右子树
class Solution {
public:
    bool hasPathSum(TreeNode *root, int sum) {
       if(root == NULL)
           return false;
        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);
    }
};

发表于 2016-09-01 14:17:09 回复(3)

使用递归求解

public class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null)
            return false;

        sum -= root.val;
        if (sum == 0 && root.left == null && root.right == null)
            return true;

        return hasPathSum(root.left, sum) || hasPathSum(root.right, sum);
    }
}
发表于 2018-07-14 07:35:26 回复(1)
//后序非递归遍历
    public boolean hasPathSum(TreeNode root, int sum) {
        if(root==null)
            return false;
        Stack<TreeNode> stack =new Stack<>();
        Stack<Integer> flag =new Stack<>();
        Stack<Integer> sumStack =new Stack<>();
        sumStack.push(0);
        while(!stack.isEmpty()||root!=null){
            while(root!=null){
                int total=sumStack.peek()+root.val;
                sumStack.push(total);
                stack.push(root);
                flag.push(0);
                root=root.left;
            }
            while(!stack.isEmpty()&&flag.peek()==1){
                TreeNode tt=stack.pop();
                if(sumStack.pop()==sum&&tt.left==null&&tt.right==null)
                    return true;
                flag.pop();
            }
            if(!stack.isEmpty()){
                TreeNode temp=stack.peek();
                flag.pop();
                flag.push(1);
                root=temp.right;
            }
        }
        return false;
    }
    //递归前序
    public boolean hasPathSum1(TreeNode root, int sum) {
        if(root==null) return false;
        if(root.left==null&&root.right==null&&root.val==sum)
            return true;
        return hasPathSum1(root.left,sum-root.val)||hasPathSum1(root.left,sum-root.val);
    }
编辑于 2017-12-08 20:10:04 回复(1)
简洁的JavaScript:
function hasPathSum( root ,  sum ) {
    // write code here
    if (root === null) return;
    if (root.val === sum && root.left === null && root.right === null) return true;
    return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
}


发表于 2021-11-05 16:59:39 回复(0)
解题思路:使用递归法
import java.util.*;
/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */
public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @param sum int整型 
     * @return bool布尔型
     */
    public boolean hasPathSum (TreeNode root, int sum) {
        // write code here
        if(root==null) return false;
        if(root.left==null&&root.right==null) return root.val==sum;
        boolean bol1=false;
        boolean bol2=false;
        if(root.left!=null) bol1=hasPathSum(root.left,sum-root.val);
        if(root.right!=null) bol2=hasPathSum(root.right,sum-root.val);
        return bol1||bol2;
    }
}


发表于 2021-03-20 16:22:11 回复(0)

深度优先遍历非递归

class Solution {
public:
    bool hasPathSum(TreeNode *root, int sum) {
        if(root==NULL)
            return false;
        vector<pair<TreeNode*,int>>stk;
        stk.push_back(make_pair(root,root->val));
        while(!stk.empty()){
            auto cur=stk.back();
            stk.pop_back();
            if(cur.first->left==NULL&&cur.first->right==NULL&&cur.second==sum)
                return true;
            if(cur.first->left!=NULL)
                stk.push_back(make_pair(cur.first->left,cur.second+cur.first->left->val));
            if(cur.first->right!=NULL)
                stk.push_back(make_pair(cur.first->right,cur.second+cur.first->right->val));
        }
        return false;
    }
};
发表于 2018-05-28 22:23:50 回复(4)
class Solution:
    def hasPathSum(self , root: TreeNode, sum: int) -> bool:
        # write code here
        if root == None:
            return False
        sum = sum - root.val
        if sum == 0 and root.left == None and root.right == None:
            return True
        root_left = self.hasPathSum(root.left, sum)
        root_right = self.hasPathSum(root.right, sum)
        return root_left or root_right
发表于 2021-11-26 19:40:14 回复(0)
class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum) {
        if(root==nullptr)
            return false;
        if(root->left==nullptr && root->right==nullptr)
            return root->val == sum;
        return hasPathSum(root->left,sum-root->val) || hasPathSum(root->right,sum-root->val);
    }
};

编辑于 2020-09-07 14:53:31 回复(0)
使用bfs,用一个队列维持根到当前节点的和
bool hasPathSum3(TreeNode* root, int sum) { //bfs
        if (!root)
        {
            return false;
        }

        queue<TreeNode*> que;
        queue<int> sum_que;
        que.push(root);
        sum_que.push(root->val);

        while (!que.empty())
        {
            TreeNode* cur = que.front();
            que.pop();
            int ret = sum_que.front();
            sum_que.pop();

            if (cur->left==NULL&&cur->right==NULL&&ret==sum)
            {
                return true;
            }
            if (cur->left)
            {
                que.push(cur->left);
                sum_que.push(ret + cur->left->val);
            }
            if (cur->right)
            {
                que.push(cur->right);
                sum_que.push(ret + cur->right->val);
            }
        }
        return false;

    }

发表于 2018-01-07 17:19:20 回复(0)