【二叉樹】從根到葉的二進制數之和

0x00 題目

給出一棵二叉樹，其上每個結點的值都是 ​

​0​

​​ 或 ​

​1​

​​ 每一條從根到葉的路徑

都代表一個從 ​

​最高​

​ 有效位開始的 ​

​二進制​

​ 數

例如，如果路徑為 0 -> 1 -> 1 -> 0 -> 1

那麼它表示二進制數 ​​

​01101​

​​，也就是 ​

​13​

​

對樹上的每一片葉子

我們都要找出從根到該葉子的路徑所表示的數字

傳回這些數字之和。題目資料保證答案是一個 32 位整數

0x01 思路

根據題目給出的示例

根節點在左邊，子節點在右邊

以題目給的示例來講解

路徑為 ​​

​0 -> 1 -> 1 -> 0 -> 1​

​​ 依次通路路徑的步驟如下：

​

​0​

​​

​01​

​​

​011​

​​

​0110​

​​

​01101​

​

換個寫法：

​​

​00000​

​​

​00001​

​​

​00011​

​​

​00110​

​​

​01101​

​

發現規律了麼？

對！左移！

使用 ​​

​<<​

​ 向左位移！

0x02 解法

語言：​

​Swift​

​

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 sumRootToLeaf(_ root: TreeNode?) -> Int {
    guard let root = root else { return 0 }

    func dfs(_ root: TreeNode?, _ val: Int) -> Int {
        guard let root = root else {
            return 0
        }

        var sum = 0
        
        // 根節點的值左移，再加上目前值
        let num = val << 1 + root.val
        
        // 到葉子節點了，傳回這一條路徑的值
        if root.left == nil && root.right == nil {
            return num
        }
        
        // 左節點不為空，繼續往下
        if root.left != nil {
            sum += dfs(root.left, num)
        }

        // 右節點不為空，繼續往下        
        if root.right != nil{
            sum += dfs(root.right, num)
        }
        
        return sum
    }

    return dfs(root, 0)
}
      

小編輯器