LeetCode.1022-根到葉路徑二進制數之和(Sum of Root To Leaf Binary Numbers)

這是小川的第381次更新，第410篇原創

01 看題和準備

今天介紹的是LeetCode算法題中Easy級别的第243題（順位題号是1022）。給定二叉樹，每個節點值為0或1.每個根到葉路徑表示以最高有效位開始的二進制數。例如，如果路徑為

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

，那麼這可能表示二進制的

01101

，即13。

對于樹中的所有葉子節點，請考慮從根到該葉子節點的路徑所代表的數字。傳回這些數字的總和。

例如：

1
    /   \
   0     1
  / \   / \
 0   1 0   1
           

輸入：[1,0,1,0,1,0,1]

輸出：22

說明：（100）+（101）+（110）+（111）= 4 + 5 + 6 + 7 = 22

注意：

• 樹中的節點數介于1和1000之間。

• node.val

  是0或1。
• 答案不會超過2^31 - 1。

02 第一種解法

遞歸的方式解題。

結合題目給的示例來看，可以将該二叉樹分為兩部分，

left

和

right

，

left

那一支有兩條路徑100和101，直接做加法就是4+5=9；

right

那一支也有兩條路徑110和111，直接做加法就是6+7=13，我們可以将求和拆分成左子樹、右子樹之和來做。

如果目前節點為空，傳回0。如果目前節點如果為葉子節點（沒有左子節點和右子節點的節點），就傳回此路徑所表示的整數。計算路徑上的二進制數，可以通用此代碼：

int val = val*2 + currentNodeValue;

，和前天的那道題目在處理累加二進制字元串上類似。

public int sumRootToLeaf(TreeNode root) {
    return getSum(root, 0);
}

public int getSum(TreeNode root, int sum) {
    if (root == null) {
        return 0;
    }
    // 換成 sum = (sum<<1) + root.val; 效果一樣
    sum = sum*2 + root.val;
    // 目前節點為葉子節點時
    if (root.left == null && root.right == null) {
        return sum;
    }
    return getSum(root.left, sum) + getSum(root.right, sum);
}
           

03 第二種解法

疊代的方式解題。借助兩個棧來實作，思路和上面類似。

public int sumRootToLeaf2(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int sum = 0;
    // 存節點
    Stack<TreeNode> stack = new Stack<TreeNode>();
    // 存路徑所代表整數
    Stack<Integer> prevSum = new Stack<Integer>();
    stack.push(root);
    prevSum.push(root.val);
    while (!stack.isEmpty()) {
        TreeNode temp = stack.pop();
        Integer tempSum = prevSum.pop();
        // 左子樹
        if (temp.left != null) {
            stack.push(temp.left);
            prevSum.push(tempSum*2 + temp.left.val);
        }
        // 右子樹
        if (temp.right != null) {
            stack.push(temp.right);
            prevSum.push(tempSum*2 + temp.right.val);
        }
        // 葉子節點，累加完整路徑所表示的整數
        if (temp.left == null && temp.right == null) {
            sum += tempSum;
        }
    }
    return sum;
}
           

04 小結

算法專題目前已連續日更超過七個月，算法題文章249+篇，公衆号對話框回複【資料結構與算法】、【算法】、【資料結構】中的任一關鍵詞，擷取系列文章合集。

以上就是全部内容，如果大家有什麼好的解法思路、建議或者其他問題，可以下方留言交流，點贊、留言、轉發就是對我最大的回報和支援！