Leetcode 404-左叶子之和

2024-09-01 04:04

文章标签 leetcode 404 叶子

本文主要是介绍Leetcode 404-左叶子之和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

给定二叉树的根节点 root ，返回所有左叶子之和。
在这里插入图片描述

题解

二叉树的题目，如果需要返回某个值，可以分左右子树递归计算，最后sum=left+right

递归三部曲：

确定递归函数的参数和返回值
判断一个树的左叶子节点之和，那么一定要传入树的根节点，递归函数的返回值为数值之和，所以为int,使用题目中给出的函数就可以了。
确定终止条件
如果遍历到空节点，那么左叶子值一定是0
确定单层递归的逻辑
当遇到左叶子节点的时候，记录数值，然后通过递归求取左子树左叶子之和，和右子树左叶子之和，相加便是整个树的左叶子之和。

代码中left为什么要分两块计算而right不用？
因为如果直接计算sumOfLeftLeaves(root.left)而root.left恰好为左叶子，则在进入root.left那一层时不再满足(root.left!=null&&root.left.left==null && root.left.right ==null)这个条件，所以left计算要分是否是左叶子两种情况计算

class Solution {public int sumOfLeftLeaves(TreeNode root) {int sum,right,left;//边界条件if(root==null) return 0;/*这里left为什么要分两块计算而right不用？因为如果直接计算sumOfLeftLeaves(root.left)而root.left恰好为左叶子，则在进入root.left那一层时不再满足(root.left!=null&&root.left.left==null&&root.left.right==null)这个条件，所以left计算要分是否是左叶子两种情况计算*///满足条件：为左叶子if(root.left!=null&&root.left.left==null&&root.left.right==null){left=root.left.val;}else{left=sumOfLeftLeaves(root.left);}right=sumOfLeftLeaves(root.right);//返回值return left+right;}
}

错误做法：

使用全局变量计算左叶子之和，遇到左叶子时返回会使得root刚好只有一个左叶子节点时就返回了，不会进入右子树

class Solution {public int res;public int sumOfLeftLeaves(TreeNode root) {dfs(root);return res;}public void dfs(TreeNode root){//为空if(root==null) return;//满足条件：左叶子，结果集+left.val//这个做法会使得root刚好只有一个左叶子节点时就返回了，不会进入右子树//为了避免这种情况，需要返回某个值而不是直接返回if(root.left!=null&&root.left.left==null&&root.left.right==null){res+= root.left.val;return; }//不为叶子节点if(root.left!=null||root.right!=null){dfs(root.left);dfs(root.right);//注意root的右子树也可能有左叶子}}
}