给定二叉树的根节点
root
,返回所有左叶子之和。示例 1:
输入: root = [3,9,20,null,null,15,7] 输出: 24 解释: 在这个二叉树中,有两个左叶子,分别是 9 和 15,所以返回 24示例 2:
输入: root = [1] 输出: 0提示:
- 节点数在
[1, 1000]
范围内-1000 <= Node.val <= 1000
Java 解题思路及代码实现
package com.java.leetcode.tree;
import com.java.leetcode.compent.TreeNode;
import java.util.Stack;
/**
* 给定二叉树的根节点 root ,返回所有左叶子之和。
*
*
*
* 示例 1:
*
*
*
* 输入: root = [3,9,20,null,null,15,7]
* 输出: 24
* 解释: 在这个二叉树中,有两个左叶子,分别是 9 和 15,所以返回 24
* 示例 2:
*
* 输入: root = [1]
* 输出: 0
*
*
* 提示:
*
* 节点数在 [1, 1000] 范围内
* -1000 <= Node.val <= 1000
*/
public class sumOfLeftLeaves404 {
/**
* 递归函数
* * 1、参数:
* * root
* * 2、终止条件:
* * 遇到叶子结点记录左叶子结点之和 其余返回0;
* * 3、确定单层递归的逻辑:
* * 遇到 左叶子节点 加和 遇到右子树做叶子结点 加和
* * 两者相加获取整体左叶子节点加和
* @param root
* @return
*/
public int sumOfLeftLeaves(TreeNode root) {
// 遍历到空节点 返回 0;
if(root==null){
return 0;
}
// 如果遍历到叶子结点 那么其值左右叶子结点也为空节点
if(root.left==null&&root.right==null){
return 0;
}
int leftnum= sumOfLeftLeaves(root.left);
//
if(root!=null&&root.left!=null&&root.left.left==null&&root.left.right==null){
// 加和
leftnum=root.left.val;
}
// 右节点
int rightnum=sumOfLeftLeaves(root.right);
int sumnum=leftnum+rightnum;
return sumnum;
}
/**
* 迭代法 :
* 通过栈的形式进行左子树之和统计\
*
* 通过前序遍历获取所有节点
* @param root
* @return
*/
public int sumOfLeftLeaves2(TreeNode root) {
int res=0;
if(root==null){
return 0;
}
Stack<TreeNode> stack=new Stack<>();
stack.push(root);
// 判断栈是否为空
while(!stack.isEmpty()){
TreeNode node=stack.pop();
// 判断是否为左叶子节点
if(node.left!=null&&node.left.left==null&&node.left.right==null){
res+=node.left.val;
}
if(node.left!=null){
stack.push(node.left);
}
if(node.right!=null){
stack.push(node.right);
}
}
return res;
}
}