1022-从根到叶的二进制数之和

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:27 2023-09-13 16:06:27 Updated    

给出一棵二叉树，其上每个结点的值都是 0 或 1 。每一条从根到叶的路径都代表一个从最高有效位开始的二进制数。

  • 例如，如果路径为 0 -> 1 -> 1 -> 0 -> 1，那么它表示二进制数 01101，也就是 13 。

对树上的每一片叶子，我们都要找出从根到该叶子的路径所表示的数字。

返回这些数字之和。题目数据保证答案是一个 32 位 整数。

示例 1：

![](https://assets.leetcode.com/uploads/2019/04/04/sum-of-root-to-leaf-binary-
numbers.png)

**输入：** root = [1,0,1,0,1,0,1]
**输出：** 22
**解释：** (100) + (101) + (110) + (111) = 4 + 5 + 6 + 7 = 22

示例 2：

**输入：** root = [0]
**输出：** 0

提示：

  • 树中的节点数在 [1, 1000] 范围内
  • Node.val 仅为 0 或 1

前言

关于二叉树后序遍历的详细说明请参考「145. 二叉树的后序遍历的官方题解 」。

方法一：递归

后序遍历的访问顺序为：左子树——右子树——根节点。我们对根节点 root 进行后序遍历：

  • 如果节点是叶子节点，返回它对应的数字 val。

  • 如果节点是非叶子节点，返回它的左子树和右子树对应的结果之和。

[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
class Solution:
    def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:
        def dfs(node: Optional[TreeNode], val: int) -> int:
            if node is None:
                return 0
            val = (val << 1) | node.val
            if node.left is None and node.right is None:
                return val
            return dfs(node.left, val) + dfs(node.right, val)
        return dfs(root, 0)
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int dfs(TreeNode *root, int val) {
        if (root == nullptr) {
            return 0;
        }
        val = (val << 1) | root->val;
        if (root->left == nullptr && root->right == nullptr) {
            return val;
        }
        return dfs(root->left, val) + dfs(root->right, val);
    }

    int sumRootToLeaf(TreeNode* root) {
        return dfs(root, 0);
    }
};
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int sumRootToLeaf(TreeNode root) {
        return dfs(root, 0);
    }

    public int dfs(TreeNode root, int val) {
        if (root == null) {
            return 0;
        }
        val = (val << 1) | root.val;
        if (root.left == null && root.right == null) {
            return val;
        }
        return dfs(root.left, val) + dfs(root.right, val);
    }
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
    public int SumRootToLeaf(TreeNode root) {
        return DFS(root, 0);
    }

    public int DFS(TreeNode root, int val) {
        if (root == null) {
            return 0;
        }
        val = (val << 1) | root.val;
        if (root.left == null && root.right == null) {
            return val;
        }
        return DFS(root.left, val) + DFS(root.right, val);
    }
}
[sol1-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int dfs(struct TreeNode *root, int val) {
    if (root == NULL) {
        return 0;
    }
    val = (val << 1) | root->val;
    if (root->left == NULL && root->right == NULL) {
        return val;
    }
    return dfs(root->left, val) + dfs(root->right, val);
}

int sumRootToLeaf(struct TreeNode* root){
    return dfs(root, 0);
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
var sumRootToLeaf = function(root) {
    const dfs = (root, val) => {
        if (!root) {
            return 0;
        }
        val = (val << 1) | root.val;
        if (!root.left&& !root.right) {
            return val;
        }
        return dfs(root.left, val) + dfs(root.right, val);
    }
    return dfs(root, 0);
};
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
func dfs(node *TreeNode, val int) int {
    if node == nil {
        return 0
    }
    val = val<<1 | node.Val
    if node.Left == nil && node.Right == nil {
        return val
    }
    return dfs(node.Left, val) + dfs(node.Right, val)
}

func sumRootToLeaf(root *TreeNode) int {
    return dfs(root, 0)
}

复杂度分析

  • 时间复杂度：O(n)，其中 n 是节点数目。总共访问 n 个节点。

  • 空间复杂度：O(n)。递归栈需要 O(n) 的空间。

方法二：迭代

我们用栈来模拟递归，同时使用一个 prev 指针来记录先前访问的节点。算法步骤如下：

  1. 如果节点 root 非空，我们将不断地将它及它的左节点压入栈中。

  2. 我们从栈中获取节点：

    • 该节点的右节点为空或者等于 prev，说明该节点的左子树及右子树都已经被访问，我们将它出栈。如果该节点是叶子节点，我们将它对应的数字 val 加入结果中。设置 prev 为该节点，设置 root 为空指针。

    • 该节点的右节点非空且不等于 prev，我们令 root 指向该节点的右节点。

  3. 如果 root 为空指针或者栈空，中止算法，否则重复步骤 1。

需要注意的是，每次出入栈都需要更新 val。

[sol2-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:
        ans = val = 0
        st = []
        pre = None
        while root or st:
            while root:
                val = (val << 1) | root.val
                st.append(root)
                root = root.left
            root = st[-1]
            if root.right is None or root.right == pre:
                if root.left is None and root.right is None:
                    ans += val
                val >>= 1
                st.pop()
                pre = root
                root = None
            else:
                root = root.right
        return ans
[sol2-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    int sumRootToLeaf(TreeNode* root) {
        stack<TreeNode *> st;
        int val = 0, ret = 0;
        TreeNode *prev = nullptr;
        while (root != nullptr || !st.empty()) {
            while (root != nullptr) {
                val = (val << 1) | root->val;
                st.push(root);
                root = root->left;
            }
            root = st.top();
            if (root->right == nullptr || root->right == prev) {
                if (root->left == nullptr && root->right == nullptr) {
                    ret += val;
                }
                val >>= 1;
                st.pop();
                prev = root;
                root = nullptr;
            } else {
                root = root->right;
            }
        }
        return ret;
    }
};
[sol2-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public int sumRootToLeaf(TreeNode root) {
        Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
        int val = 0, ret = 0;
        TreeNode prev = null;
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                val = (val << 1) | root.val;
                stack.push(root);
                root = root.left;
            }
            root = stack.peek();
            if (root.right == null || root.right == prev) {
                if (root.left == null && root.right == null) {
                    ret += val;
                }
                val >>= 1;
                stack.pop();
                prev = root;
                root = null;
            } else {
                root = root.right;
            }
        }
        return ret;
    }
}
[sol2-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public class Solution {
    public int SumRootToLeaf(TreeNode root) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        int val = 0, ret = 0;
        TreeNode prev = null;
        while (root != null || stack.Count > 0) {
            while (root != null) {
                val = (val << 1) | root.val;
                stack.Push(root);
                root = root.left;
            }
            root = stack.Peek();
            if (root.right == null || root.right == prev) {
                if (root.left == null && root.right == null) {
                    ret += val;
                }
                val >>= 1;
                stack.Pop();
                prev = root;
                root = null;
            } else {
                root = root.right;
            }
        }
        return ret;
    }
}
[sol2-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#define MAX_NODE_SIZE 1000

int sumRootToLeaf(struct TreeNode* root) {
    struct TreeNode ** stack = (struct TreeNode **)malloc(sizeof(struct TreeNode *) * MAX_NODE_SIZE);
    int top = 0;
    int val = 0, ret = 0;
    struct TreeNode *prev = NULL;
    while (root != NULL || top) {
        while (root != NULL) {
            val = (val << 1) | root->val;
            stack[top++] = root;
            root = root->left;
        }
        root = stack[top - 1];
        if (root->right == NULL || root->right == prev) {
            if (root->left == NULL && root->right == NULL) {
                ret += val;
            }
            val >>= 1;
            top--;
            prev = root;
            root = NULL;
        } else {
            root = root->right;
        }
    }
    free(stack);
    return ret;
}
[sol2-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
var sumRootToLeaf = function(root) {
    const stack = [];
    let val = 0, ret = 0;
    let prev = null;
    while (root || stack.length) {
        while (root) {
            val = (val << 1) | root.val;
            stack.push(root);
            root = root.left;
        }
        root = stack[stack.length - 1];
        if (!root.right || root.right === prev) {
            if (!root.left && !root.right) {
                ret += val;
            }
            val >>= 1;
            stack.pop();
            prev = root;
            root = null;
        } else {
            root = root.right;
        }
    }
    return ret;
};
[sol2-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func sumRootToLeaf(root *TreeNode) (ans int) {
    val, st := 0, []*TreeNode{}
    var pre *TreeNode
    for root != nil || len(st) > 0 {
        for root != nil {
            val = val<<1 | root.Val
            st = append(st, root)
            root = root.Left
        }
        root = st[len(st)-1]
        if root.Right == nil || root.Right == pre {
            if root.Left == nil && root.Right == nil {
                ans += val
            }
            val >>= 1
            st = st[:len(st)-1]
            pre = root
            root = nil
        } else {
            root = root.Right
        }
    }
    return
}

复杂度分析

  • 时间复杂度：O(n)，其中 n 是节点数目。总共访问 n 个节点。

  • 空间复杂度：O(n)。栈最多压入 n 个节点。

 Comments
On this page
1022-从根到叶的二进制数之和