乐趣区

关于算法: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)
        }
        
    }

github 链接

退出移动版