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

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

题目描述

给定一个二叉树root和一个值 sum ，判断是否有从根节点到叶子节点的节点值之和等于 sum 的路径。

1.该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点

2.叶子节点是指没有子节点的节点

3.路径只能从父节点到子节点，不能从子节点到父节点

4.总节点数目为n

方法一：递归思想

解题思路

针对方法一，我们采用递归的思想进行解决。(对于二叉树的题目，往往会想到递归，即终止条件、当前步骤、如何下次递归进行思考，然后解决问题)我们递归遍历二叉树的路径节点，计算二叉树路径节点的数字之和，若到达叶子节点且路径的数字之和等于sum，则说明二叉树中存在节点和为指定值的路径。

解题代码

class Solution {
public:
    bool 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);
    }
};

复杂度分析

时间复杂度：最坏的情况递归所有的节点，因此时间复杂度为$O(N)O(N)$。

空间复杂度：为二叉树的深度，因此空间复杂度为$O(logN)O(logN)$，但若二叉树遇到最坏情况，退化为链表，则其空间复杂度为$O(N)O(N)$

方法二：层次遍历方法

解题思路

我们也可以使用层次遍历的方法，即对二叉树的每一层进行遍历，直到叶节点，然后判断是否有路径使得其值等于已知的值。

解题代码

class Solution {
public:
    struct path_sum{
        TreeNode* node;
        int cur_sum;
        path_sum(TreeNode* root = NULL, int value = 0):node(root),cur_sum(value){};
    };//自定义path_sum 用于表示到节点的路径和
    bool hasPathSum(TreeNode* root, int sum) {
        if(!root) return false;
        queue<path_sum*> q;
        path_sum* head = new path_sum(root,root->val);  //以头节点构造一个path_sum
        q.push(head);
        //队列不为空
        while(!q.empty()){
            path_sum* tmp = q.front(); // 取出一个path_sum
            q.pop();
            if(tmp->node->left==NULL&&tmp->node->right==NULL) //如果为叶子节点
            {
                if(tmp->cur_sum==sum) return true; //判断与sum的关系
            }else{
                if(tmp->node->left)//如果具有左节点
                {
                    int left_sum = tmp->node->left->val+tmp->cur_sum;
                    path_sum* left = new path_sum(tmp->node->left,left_sum);
                    q.push(left);
                }
                if(tmp->node->right)//如果有右节点
                {
                    int right_sum = tmp->node->right->val+tmp->cur_sum;
                    path_sum* right = new path_sum(tmp->node->right,right_sum);
                    q.push(right);
                }    
            }
        }
        return false;
    }
};

复杂度分析

时间复杂度：最坏情况为树退化为链表，时间复杂度为$O(N)O(N)$

空间复杂度：使用队列辅助空间，且最坏情况为二叉树退化为链表，因此空间复杂度为$O(N)O(N)$