『LeetCode』1022 从根到叶的二进制数之和

题目

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

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

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

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

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

示例 1：

输入：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

---

题解

【从根到叶的二进制数之和】『递归』&『迭代』

递归

根据二进制的性质，结点代表的值为 \((\text{父节点代表的值} \times 2 + \text{当前结点代表的值})\)，然后按照常规递归遍历二叉树的方法遍历即可

# Code language: Python
class Solution:
    def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:
        ans = 0
        def dfs(root, r):
            if root:
                val = (r << 1) + root.val
                if root.left:
                    dfs(root.left, val)
                if root.right:
                    dfs(root.right, val)
                if not root.left and not root.right:
                    nonlocal ans
                    ans += val
        
        dfs(root, 0)
        return ans

// Code language: Cpp
class Solution {
public:
    int sumRootToLeaf(TreeNode *root) {
        int ans = 0;
        function<void(TreeNode *, int)> dfs = [&](TreeNode *root, int r) {
            int val = (r << 1) + root->val;
            if (root->left != nullptr) dfs(root->left, val);
            if (root->right != nullptr) dfs(root->right, val);
            if (root->left == nullptr && root->right == nullptr) ans += val;
            return val;
        };
        if (root != nullptr) dfs(root, 0);
        return ans;
    }
};

// Code language: Java
class Solution {
    int ans = 0;
    public int sumRootToLeaf(TreeNode root) {
        if (root != null) dfs(root, 0);
        return ans;
    }

    public void dfs(TreeNode root, int r) {
        int val = (r << 1) + root.val;
        if (root.left != null) dfs(root.left, val);
        if (root.right != null) dfs(root.right, val);
        if (root.left == null && root.right == null) ans += val;
    }
}

不使用全局变量，通过函数返回值返回结果的写法:

# Code language: Python
class Solution:
    def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:
        def dfs(root, r):
            ans = 0
            if root:
                val = (r << 1) + root.val
                if root.left:
                    ans += dfs(root.left, val)
                if root.right:
                    ans += dfs(root.right, val)
                if not root.left and not root.right:
                    ans += val
            return ans
        
        return dfs(root, 0)

// Code language: Cpp
class Solution {
public:
    int sumRootToLeaf(TreeNode *root) {
        function<int(TreeNode *, int)> dfs = [&dfs](TreeNode *root, int r) {
            int val = (r << 1) + root->val, ans = 0;
            if (root->left != nullptr) ans += dfs(root->left, val);
            if (root->right != nullptr) ans += dfs(root->right, val);
            if (root->left == nullptr && root->right == nullptr) ans += val;
            return ans;
        };
        return root == nullptr ? 0 : dfs(root, 0);
    }
};

// Code language: Java
class Solution {
    public int sumRootToLeaf(TreeNode root) {
        return root == null ? 0 : dfs(root, 0);
    }

    public int dfs(TreeNode root, int r) {
        int val = (r << 1) + root.val, ans = 0;
        if (root.left != null) ans += dfs(root.left, val);
        if (root.right != null) ans += dfs(root.right, val);
        if (root.left == null && root.right == null) ans += val;
        return ans;
    }
}

• 时间复杂度: \(O(n)\), \(n\) 为二叉树结点个数
• 空间复杂度: \(O(n)\), 递归栈的开销

---

迭代

将递归的代码转为迭代，可其余部分与二叉树的遍历相同，这里前中后层序遍历均可用，简单起见使用前序遍历。

# Code language: Python
class Solution:
    def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:
        ans = 0

        # 栈中存（结点，父节点代表的二进制数）
        st = list()
        if root:
            st.append((root, 0))
        
        while st:
            cur, val = st.pop()
            val = (val << 1) + cur.val
            if not cur.left and not cur.right:
                ans += val
            if cur.right:
                st.append((cur.right, val))
            if cur.left:
                st.append((cur.left, val))
        return ans

// Code language: Cpp
class Solution {
public:
    int sumRootToLeaf(TreeNode *root) {
        int ans;
        stack<pair<TreeNode *, int>> st;
        if (root != nullptr) st.emplace(pair{root, 0});
        while (!st.empty()) {
            auto &p = st.top();
            TreeNode *cur = p.first;
            int val = (p.second << 1) + cur->val;
            st.pop();
            if (cur->right != nullptr) st.emplace(pair{cur->right, val});
            if (cur->left != nullptr) st.emplace(pair{cur->left, val});
            if (cur->left == nullptr && cur->right == nullptr) ans += val;
        }
        return ans;
    }
};

// Code language: Java
class Solution {
    public int sumRootToLeaf(TreeNode root) {
        int ans = 0;
        Deque<TreeNode> st = new ArrayDeque<>();
        Deque<Integer> v = new ArrayDeque<>();
        if (root != null) {
            st.addLast(root);
            v.addLast(0);
        }
        while (!st.isEmpty()) {
            TreeNode cur = st.pollLast();
            int val = (v.pollLast() << 1) + cur.val;
            if (cur.left != null) {
                st.addLast(cur.left);
                v.addLast(val);
            }
            if (cur.right != null) {
                st.addLast(cur.right);
                v.addLast(val);
            }
            if (cur.left == null && cur.right == null)
                ans += val;
        }
        return ans;
    }
}

• 时间复杂度: \(O(n)\), \(n\) 为二叉树结点个数
• 空间复杂度: \(O(n)\), 递归栈的开销

---

最后

如果对你有帮助的话，请给我点个赞吧~

欢迎前往 我的博客 或 Github 查看更多题解