题意分析

  • 这个题目就是要我们找出从根结点到叶子结点的所有的数字，然后我们需要将这些数字拼接成一个数，将所有的数相加起来就是我们的答案了。

  • 前置知识，DFS。对于DFS我们可以想象成一棵树，我们需要不断递归到树的最下面的叶子节点。

思路分析

思路一 DFS

  • 我们对整棵二叉树进行递归操作，同时我们将当前位置拼接成的数字记录下来，直到遇到根节点之后就累加到答案里面。这里判断叶子节点的时候需要同时判断这个节点没有左右叶子节点。如果这棵树很高的话，最后计算出来的结果很可能会需要高精度来写。但是我们发现返回的参数是int类型的。所以就没有必要了。

  • 如下图
    图片说明

  • 代码如下

    • 在进行DFS的时候可能存在遍历所有的结点的情况，时间复杂度为O(n)
    • 需要存储所有的结点的信息，空间复杂度为O(n) 
/**
 * struct TreeNode {
 *    int val;
 *    struct TreeNode *left;
 *    struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    int ans=0;
    void dfs(TreeNode* now,int sum){
        // 这个结点没有左右子节点，说明这个这个就是叶子结点
        if(now->left==NULL&&now->right==NULL){
            ans+=sum;
            return;
        }
        if(now->left){
            dfs(now->left,sum*10+now->left->val);
        }
        if(now->right){
            dfs(now->right,sum*10+now->right->val);
        }
    }
    int sumNumbers(TreeNode* root) {
        // write code here
        // 特判根节点为空的情况
        if(!root){
            return 0;
        }
        dfs(root,root->val);
        return ans;
    }
};

解法二 BFS

  • 既然可以使用DFS进行求解，那么我们可以尝试一下是否可以使用BFS进行求解，因为BFS如果递归太深了的话很可能会造成爆栈的情况。所以我们可以使用BFS利用队列来处理每一种状态。我们先定义一个结构体。 
struct node{
        TreeNode* tree; // 用来存储当前的节点
        int val; // 用来存储当前位置拼接而成的值
    }Node;

我们用这个结构体可以帮助我们记录每一个位置的状态。然后对于这些位置，我们就可以继续向下进行遍历了。其余情况还是和DFS进行一样的处理。

  • 代码如下
    • 在进行BFS的时候会遍历所有的结点，时间复杂度为O(n)
    • 需要存储所有的结点的信息，空间复杂度为O(n) 
/**
 * struct TreeNode {
 *    int val;
 *    struct TreeNode *left;
 *    struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    // 定义一个结构体来存储每个位置的状态
    struct node{
        TreeNode* tree;
        int val;
    }Node;
    queue<node> q;
    int sumNumbers(TreeNode* root) {
        // write code here
        // 特判空根结点的情况
        if(!root){
            return 0;
        }
        // 初始化
        int ans=0;
        Node.tree=root;
        Node.val=root->val;
        q.push(Node);
        while(!q.empty()){
            node now = q.front();
            q.pop();
            // 如果这个结点是叶子结点
            if(now.tree->left==NULL&&now.tree->right==NULL){
                ans+=now.val;
            }
            // 对左子结点进行继续遍历
            if(now.tree->left){
                // 记录这个位置的状态
                Node.tree=now.tree->left;
                Node.val=now.val*10+now.tree->left->val;
                q.push(Node);
            }
            // 对右子结点进行遍历
            if(now.tree->right){
                // 记录这个位置的状态
                Node.tree=now.tree->right;
                Node.val=now.val*10+now.tree->right->val;
                q.push(Node);
            }
        }
        return ans;
    }
};