力扣1022题：从根到叶的二进制数之和 - 递归解法详解

内容简介

本文详细解析了力扣第1022题"从根到叶的二进制数之和"的递归解法。通过深度优先遍历二叉树，累计每条路径表示的二进制数值，最终得到所有路径数值之和。这种方法时间复杂度为O(n)，是理解二叉树遍历和位运算结合的经典解法。文章包含完整注释代码、算法思路讲解和复杂度分析。

算法思路

1‌.递归遍历‌：使用深度优先搜索(DFS)遍历二叉树

‌2.路径累计‌：在遍历过程中维护当前路径的二进制数值

‌3.叶节点处理‌：到达叶节点时将完整路径值累加到结果中

‌4.位运算优化‌：使用位运算代替乘法运算提高效率

代码实现（带详细注释）

class Solution {
public:
    int ret = 0;  // 存储最终结果的变量
    
    // 递归辅助函数：计算从根到叶的二进制数之和
    void sumroot(TreeNode* root, int pre) {
        if (!root) {  // 空节点直接返回
            return;
        }
        
        // 当前节点是叶节点时，计算完整路径值并累加
        if (!root->left && !root->right) {
            ret += root->val + pre * 2;  // pre*2相当于左移一位
            return;
        }
        
        // 递归处理左右子树，更新当前路径值
        sumroot(root->left, pre * 2 + root->val);  // 等价于(pre << 1) | root->val
        sumroot(root->right, pre * 2 + root->val);
    }
    
    // 主函数：计算从根到叶的二进制数之和
    int sumRootToLeaf(TreeNode* root) {
        sumroot(root, 0);  // 从根节点开始，初始路径值为0
        return ret;
    }
};

复杂度分析

‌时间复杂度‌：O(n)，需要访问每个节点一次

‌空间复杂度‌：O(h)，递归栈空间，h为树的高度

优化方向

‌迭代实现‌：使用栈代替递归，避免递归带来的额外开销

‌位运算优化‌：使用位运算(pre << 1) | root->val代替乘法运算

‌并行处理‌：对于大型树结构，可以考虑并行处理左右子树

总结

本文提供的递归解法是从根到叶二进制数求和问题的高效解决方案，通过DFS遍历和路径累计，实现了简洁明了的算法实现。理解这种解法有助于掌握二叉树遍历和位运算的应用技巧。