1. 首页
  2. IT资讯

Leetcode 第 1022 题: 从根结点到叶子结点的二进制数字之和

从根结点到叶子结点的二进制数字之和

提供一个二进制树,每个结点的值是 0 或者 1.
每一条从根结点到叶子结点的路径,代表一个二进制的数字路径 0 -> 1 -> 1 -> 0 -> 1, 代表二进制 01101, 10 进制是 13


思路自然是递归,一条路径的值,是叶子结点的值 + 上层的值 * 2

深度优先遍历,求取深度的时候,顺便把结点的值代入计算

下面是两个计算方式稍有不同的算法


    
    // 遍历的时候,带着走的是这个结点上层的值
    
    
    func sum(node n: TreeNode?, sum above: Int?) -> Int{
        guard let dot = n else {
            return 0
        }
        let val = above ?? 0
        if dot.left == nil, dot.right == nil {
            //  print(dot.val + val)
            return dot.val + val
        }
        else{
        
        // 进入下一层结点的时候,
        // 上一层的值 + 该结点的值, 再 * 2
        // 就是下一层结点的上一层的值
            let reduce = (val + dot.val) * 2
            return sum(node: dot.left, sum: reduce) + sum(node: dot.right, sum: reduce)
        }
    }
    
    
    func sumRootToLeaf(_ root: TreeNode?) -> Int {
        guard let n = root else {
            return 0
        }
        return sum(node: n, sum: nil)

    }

func sumRootTo(leaf root: TreeNode?) -> Int {
        guard let n = root else {
            return 0
        }
        return dfs(leaf: n, value: 0)

    }
    
    // 结点的路径之和,自然是左边路径与右边路径之和
    // 计算左边路径的结果时,要带入该结点的值
    
    
    // 遍历的时候,带着走的是这个结点的值
    func dfs(leaf root: TreeNode?, value val: Int) -> Int{
        guard let n = root else {
            return 0
        }
        let reduce = val * 2 + n.val
        if n.left == nil, n.right == nil{
            return reduce
        }
        else{
            return dfs(leaf: n.left, value: reduce) + dfs(leaf: n.right, value: reduce)
        }
        
    }

本文来自投稿,不代表程序员编程网立场,如若转载,请注明出处:http://www.cxybcw.com/199652.html

联系我们

13687733322

在线咨询:点击这里给我发消息

邮件:1877088071@qq.com

工作时间:周一至周五,9:30-18:30,节假日休息

QR code