剑指 Offer II 049. 从根节点到叶节点的路径数字之和（深度优先搜索、广度优先搜索）

本题考查深度优先搜索，广度优先搜索
c++实现

//方法一：深度优先搜索
class Solution {
public:
    int dfs(TreeNode* root,int prevsum)
    {
        //根节点判空
        if(root == nullptr)
        {
            return 0;
        }
        int sum = prevsum*10+root->val;
        if(root->left == nullptr && root->right == nullptr)
        {
            return sum;
        }
        else
        {
            return dfs(root->left,sum)+dfs(root->right,sum);
        }
    }
    int sumNumbers(TreeNode* root) {
        return dfs(root,0);
    }
};

//方法二：广度优先搜索
class Solution {
public:
    int sumNumbers(TreeNode* root) {
        //根节点判空
        if(root == nullptr)
        {
            return 0;
        }
        int sum = 0;
        queue<TreeNode*> nodequeue;
        queue<int> numqueue;
        nodequeue.push(root);
        numqueue.push(root->val);
        while(!nodequeue.empty())
        {
            TreeNode* node = nodequeue.front();
            int num = numqueue.front();
            nodequeue.pop();
            numqueue.pop();
            TreeNode* left = node->left;
            TreeNode* right = node->right;
            if(left == nullptr && right == nullptr)
            {
                sum += num;
            }else{
                if (left!=nullptr) {
                    nodequeue.push(left);
                    numqueue.push(num*10 + left->val);
                }
                if(right!=nullptr)
                {
                    nodequeue.push(right);
                    numqueue.push(num*10 + right->val);
                }
            }
        }
        return sum;
    }
};

golang实现

//广度优先
func sumNumbers(root *TreeNode) int {
    var nodequeue []*TreeNode
    var numqueue []int
    var sum int
    nodequeue = append(nodequeue,root)
    numqueue = append(numqueue,root.Val)
    for len(nodequeue)>0 {
        node := nodequeue[0]
        num := numqueue[0]
        nodequeue = nodequeue[1:]
        numqueue = numqueue[1:]
        if node.Left==nil && node.Right==nil {
            sum += num
        }else{
            if node.Left != nil {
                nodequeue = append(nodequeue,node.Left)
                numqueue = append(numqueue,num*10+node.Left.Val)
            }
            if node.Right != nil {
                nodequeue = append(nodequeue,node.Right)
                numqueue = append(numqueue,num*10+node.Right.Val)
            }
        }
    }
    return sum
}

//深度优先
func dfs(node *TreeNode,prevsum int) int {
    if node == nil {
        return 0
    }
    sum := prevsum*10 + node.Val
    if node.Left == nil && node.Right == nil {
        return sum
    }
    return dfs(node.Left,sum)+dfs(node.Right,sum)
}
func sumNumbers(root *TreeNode) int {
   return dfs(root,0)
}

深度优先复杂度分析

时间复杂度：O(n)，其中 n 是二叉树的节点个数。

对每个节点访问一次。

空间复杂度：O(n)，其中 n是二叉树的节点个数。

空间复杂度主要取决于递归调用的栈空间，递归栈的深度等于二叉树的高度，最坏情况下，二叉树的高度等于节点个数，空间复杂度为O(n)。

广度优先复杂度分析

时间复杂度：O(n)，其中 n是二叉树的节点个数。

对每个节点访问一次。

空间复杂度：O(n)，其中 n 是二叉树的节点个数。

空间复杂度主要取决于队列，每个队列中的元素个数不会超过 n。