112-路径总和Ⅰ

编程我只用CPP

2018 年 10 月 04 日

22 次浏览

暂无评论

2775字数

数据结构和算法

作者：LeetCode

链接：112. 路径总和

来源：力扣（LeetCode）

著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

一、题目描述

给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

说明：叶子节点是指没有子节点的节点。

示例:

给定如下二叉树，以及目标和sum = 22：

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1

返回true, 因为存在目标和为 22 的根节点到叶子节点的路径5->4->11->2。

二、题解

2.1 dfs深搜（递归）

算法：

利用递归深度优先搜索每个节点，每经过一个节点，sum值减去当前节点的值，继续搜索子节点。直到叶子节点的时候判断sum，为0返回true，否则返回false。

代码：

class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum) {
        if (root == NULL) {
            return false;
        }
        sum -= root->val;

        // 搜索到叶子节点了
        if (root->left == NULL && root->right == NULL) {
            return sum == 0;
        }

        // 计算左右子节点
        return hasPathSum(root->left, sum) || hasPathSum(root->right, sum);
    }
};

复杂度分析

时间复杂度：我们访问每个节点一次，时间复杂度为O(N)，其中N是节点个数。
空间复杂度：最坏情况下，整棵树是非平衡的，例如每个节点都只有一个孩子，递归会调用N次（树的高度），因此栈的空间开销是O(N) 。但在最好情况下，树是完全平衡的，高度只有 log(N)，因此在这种情况下空间复杂度只有O(log(N)) 。

2.2 bfs广搜（迭代）

算法：

我们可以用栈将递归转成迭代的形式,深度优先搜索在除了最坏情况下都比广度优先搜索更快。最坏情况是指满足目标和的 root->leaf 路径是最后被考虑的，这种情况下深度优先搜索和广度优先搜索代价是相通的。

使用迭代的思路是：利用队列，每次保存当前节点以及剩余的sum，如果是叶子节点并且剩余的sum为0则返回true。否则，把节点的左右子节点分别压入队列，更新sum值。

所以我们从包含根节点的栈开始模拟，剩余目标和为 sum - root.val，然后开始迭代。弹出当前元素，如果当前剩余目标和为 0 并且在叶子节点上返回 True；如果剩余和不为零并且还处在非叶子节点上，将当前节点的所有孩子以及对应的剩余和压入栈中。

struct NodeSum {
    TreeNode *node; // 当前节点
    int sum; // 剩余的和
};

class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum) {
        queue<NodeSum *> q;
        NodeSum* p;

        TreeNode *node;
        int residualSum;

        if (root == NULL) {
            return false;
        }
        q.push(new NodeSum{ root, sum });

        while (q.empty() == false) {
            p = q.front();
            q.pop();

            node = p->node;
            // 计算剩余需要的sum
            residualSum = p->sum - node->val;
            delete p;
            
            // 存在左子节点，压入队列
            if (node->left) {
                q.push(new NodeSum{ node->left, residualSum });
            }
            // 存在右子节点，压入队列
            if (node->right) {
                q.push(new NodeSum{ node->right, residualSum });
            }
            
            // 叶子节点，sum为0
            if (node->left == NULL && node->right == NULL && residualSum == 0) {
                return true;
            }
        }
        return false;
    }
};