LeetCode 二叉树和递归专题 3：注意递归的终止条件

例1：LeetCode 第 112 题：Path Sum

传送门：112. 路径总和。

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

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

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

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

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

分析：给出一棵二叉树以及一个数组 sum，判断在这棵二叉树上是否存在一条从根到叶子结点的路径，这条路径上所有的结点的和为 sum。

下面给出一个很容易想到，但是是个错误的解答。

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

public class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) {
            return sum == 0;
        }
        if (root.left != null) {
            return hasPathSum(root.left, sum - root.val);
        }
        if (root.right != null) {
            return hasPathSum(root.right, sum - root.val);
        }
        return false;
    }
}

这样的写法，之所以是错误的，是因为我们没有注意到所求的路径是从根结点到叶子结点的路径，忽略了叶子结点这个条件，为此，我们改写方法如下：

Java 代码：

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

public class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) {
            return false;
        }
        // 是叶子结点，这就是递归到底的情况了
        if (root.left == null && root.right == null) {
            return root.val == sum;
        }
        if (hasPathSum(root.left, sum - root.val)) {
            return true;
        }
        if (hasPathSum(root.right, sum - root.val)) {
            return true;
        }
        return false;
    }
}

Python 代码：

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
# 112. 路径总和
# 给定一个二叉树和一个目标和，判断该树中是否存在根结点到叶子结点的路径，这条路径上所有结点值相加等于目标和。
#
# 说明: 叶子结点是指没有子结点的结点。


class Solution:
    def hasPathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: bool
        """
        if root is None:
            return False
        # 此时 root 不为空
        # 左边看一看，右边看一看
        # 【重点】一定要记得判断，左边子树和右边子树同时为空，说明走到底了
        if root.left is None and root.right is None and root.val == sum:
            return True
        left_has = self.hasPathSum(root.left, sum - root.val)
        right_has = self.hasPathSum(root.right, sum - root.val)
        return left_has or right_has

练习1：LeetCode 第 111 题：二叉树的最小深度

这是上一节的一个问题，权当复习吧。

练习2：LeetCode 第 404 题：左叶子之和

传送门：404. 左叶子之和。

计算给定二叉树的所有左叶子之和。

示例：

    3
   / \
  9  20
    /  \
   15   7

在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24

Python 代码：使用递归。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

# 404. 左叶子之和
# 计算给定二叉树的所有左叶子之和。

class Solution:

    # 关键在于判断是否是左边叶子结点
    def sumOfLeftLeaves(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if root is None:
            return 0
        # 1、左边非空
        # 2、左边的左边是空
        # 3、左边的右边是空
        if root.left is not None and root.left.left is None and root.left.right is None:
            return root.left.val + self.sumOfLeftLeaves(root.right)
        return self.sumOfLeftLeaves(root.left) + self.sumOfLeftLeaves(root.right)

Python 代码：BFS 的时候，拿出有左结点，并且左结点还得是叶子结点。

class Solution:

    # 关键在于判断是否是左边叶子结点
    def sumOfLeftLeaves(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if root is None:
            return 0

        queue = [root]
        res = 0
        while queue:
            top = queue.pop(0)
            if top.left and top.left.left is None is top.left.right is None:
                res += top.left.val
            if top.left:
                queue.append(top.left)
            if top.right:
                queue.append(top.right)
        return res

（本节完）