左叶子之和
LeetCode404. 左叶子之和
题目描述
给定二叉树的根节点 root ，返回所有左叶子之和。
思考
左叶子的明确定义：节点A的左孩子不为空，且左孩子的左右孩子都为空（说明是叶子节点），那么A节点的左孩子为左叶子节点
无法对当前节点直接判断是不是左叶子节点，必须要通过父节点来判断其左孩子是不是左叶子
递归的遍历顺序为后序遍历（左右中），因为要通过递归函数的返回值来累加求取左叶子数值之和
- 确定递归函数的参数和返回值
- 确定终止条件
- 确定单层递归的逻辑
- 当遇到左叶子节点的时候，记录数值
- 通过递归求取根节点的 左子树左叶子之和 和 右子树左叶子之和，相加便是整个树的左叶子之和
代码
Go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
func sumOfLeftLeaves(root *TreeNode) int {
var res int //定义变量res 结果集
findLeft(root, &res)
return res
}
//递归DFS搜索到所有左叶子节点,和值计入res
func findLeft(root *TreeNode, res *int) {
//以传入节点为根节点的 左孩子非空 且 该左孩子的左右孩子为空(是叶子节点)
if root.Left != nil && root.Left.Left == nil && root.Left.Right == nil {
//将该左孩子的节点值加入结果集res
*res = *res + root.Left.Val
}
//以传入节点为根节点的 左孩子非空 但 该左孩子的左右孩子至少一个非空(不是叶子节点)
if root.Left != nil {
findLeft(root.Left, res) //递归
}
//以传入节点为根节点的 右孩子非空 但 该右孩子的左右孩子至少一个非空(不是叶子节点)
if root.Right != nil {
findLeft(root.Right, res) //递归
}
}
|
Link
GitHub