【二叉树】左叶子之和

  • 时间:
  • 浏览:
  • 来源:互联网

0x00 题目

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


0x01 思路

叶子节点是指 没有子节点 的节点。
左节点 就是 root.left
左叶子节点 就是
root.left.left == nil && root.left.right == nil


0x02 解法

语言:Swift

树节点:TreeNode

public class TreeNode {
    public var val: Int
    public var left: TreeNode?
    public var right: TreeNode?
    public init() { self.val = 0; self.left = nil; self.right = nil; }
    public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
    public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
        self.val = val
        self.left = left
        self.right = right
    }
}

递归方式:

func sumOfLeftLeaves(_ root: TreeNode?) -> Int {
    // 节点为空,返回
    if root == nil { return 0 }
    
	// 左子树的和
    let left = sumOfLeftLeaves(root?.left)

	// 右子树的和
    let right = sumOfLeftLeaves(root?.right)
    
    // 统计
    var sum = 0
    
	// 左节点
    if let left = root?.left {
    	// 叶子节点
        if left.left == nil && left.right == nil {
            sum += left.val  // 统计
        }
    }
    
    return sum + left + right
}

小编辑器

请添加图片描述


本文链接http://metronic.net.cn/metronic/show-53449.html