• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

二叉树:递归函数究竟什么时候需要返回值,什么时候不要返回值?

开发技术 开发技术 2周前 (05-02) 5次浏览

112. 路径总和

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum ,判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标和 targetSum 。

叶子节点是指没有子节点的节点。
二叉树:递归函数究竟什么时候需要返回值,什么时候不要返回值?

输入:root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出:true

思路

如果需要搜索整颗二叉树,那么递归函数就不要返回值,如果要搜索其中一条符合条件的路径,递归函数就需要返回值,因为遇到符合条件的路径了就要及时返回。

513.找树左下角的值中,因为要遍历树的所有路径,找出深度最深的叶子节点,所以递归函数不要返回值。

本题我们要找一条符合条件的路径,所以递归函数需要返回值,及时返回。

  1. 确定递归函数的参数和返回类型
    参数:需要二叉树的根节点,还需要一个计数器,这个计数器用来计算二叉树的一条边之和是否正好是目标和,计数器为int型(sum = sum – root.val)。
    递归函数需要返回值,可以用bool类型表示。

  2. 确定终止条件
    如果最后count == 0,同时到了叶子节点的话,说明找到了目标和。
    如果遍历到了叶子节点,count不为0,就是没找到。

if (!cur->left && !cur->right && count == 0) return true; // 遇到叶子节点,并且计数为0
if (!cur->left && !cur->right) return false; // 遇到叶子节点而没有找到合适的边,直接返回
  1. 确定单层递归的逻辑
    因为终止条件是判断叶子节点,所以递归的过程中就不要让空节点进入递归了。
    递归函数是有返回值的,如果递归函数返回true,说明找到了合适的路径,应该立刻返回。
if (cur->left) { // 左 (空节点不遍历)
    // 遇到叶子节点返回true,则直接返回true
    if (traversal(cur->left, count - cur->left->val)) return true; // 注意这里有回溯的逻辑
}
if (cur->right) { // 右 (空节点不遍历)
    // 遇到叶子节点返回true,则直接返回true
    if (traversal(cur->right, count - cur->right->val)) return true; // 注意这里有回溯的逻辑
}
return false;

代码

精简后:

class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) return false;
        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);
    }
}

喜欢 (0)