作者: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);
    }
};

imagef9574f9026222914.png

复杂度分析

  • 时间复杂度:我们访问每个节点一次,时间复杂度为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;
    }
};

复杂度分析:

  • 时间复杂度:和递归方法相同是O(N)。
  • 空间复杂度:当树不平衡的最坏情况下是O(N) 。在最好情况(树是平衡的)下是 O(log(N))。
最后修改:2019 年 12 月 06 日
喜欢就给我点赞吧