[LeetCode]129.Sum Root to Leaf Numbers

简介:

【题目】

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

For example,

    1
   / \
  2   3

The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.

Return the sum = 12 + 13 = 25.

【分析】

每到一个叶子节点就代表一条路径的结束,一个值的产生。累加每个值。

【代码】

/*********************************
*   日期:2014-12-30
*   作者:SJF0115
*   题目: 129.Sum Root to Leaf Numbers
*   来源:https://oj.leetcode.com/problems/sum-root-to-leaf-numbers/
*   结果:AC
*   来源:LeetCode
*   博客:
*   时间复杂度:O(n)
*   空间复杂度:O(logn)
**********************************/
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

// 二叉树节点
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    int sumNumbers(TreeNode *root) {
        if(root == NULL){
            return 0;
        }//if
        return SumNumbers(root,0);
    }
private:
   int SumNumbers(TreeNode* node,int curSum){
       if(node == NULL){
           return 0;
       }//if
       curSum = curSum*10 + node->val;
       // 到达叶子节点返回该路径上的值
       if(node->left == NULL && node->right == NULL){
           return curSum;
       }
       // 左子树
       int leftSum = SumNumbers(node->left,curSum);
       // 右子树
       int rightSum = SumNumbers(node->right,curSum);
       return leftSum + rightSum;
   }
};
// 创建二叉树
TreeNode* CreateTreeByLevel(vector<int> num){
    int len = num.size();
    if(len == 0){
        return NULL;
    }//if
    queue<TreeNode*> queue;
    int index = 0;
    // 创建根节点
    TreeNode *root = new TreeNode(num[index++]);
    // 入队列
    queue.push(root);
    TreeNode *p = NULL;
    while(!queue.empty() && index < len){
        // 出队列
        p = queue.front();
        queue.pop();
        // 左节点
        if(index < len && num[index] != -1){
            // 如果不空创建一个节点
            TreeNode *leftNode = new TreeNode(num[index]);
            p->left = leftNode;
            queue.push(leftNode);
        }
        index++;
        // 右节点
        if(index < len && num[index] != -1){
            // 如果不空创建一个节点
            TreeNode *rightNode = new TreeNode(num[index]);
            p->right = rightNode;
            queue.push(rightNode);
        }
        index++;
    }//while
    return root;
}

int main() {
    Solution solution;
    // -1代表NULL
    vector<int> num = {1,2,3,4,-1,-1,5};
    TreeNode* root = CreateTreeByLevel(num);
    cout<<solution.sumNumbers(root)<<endl;
}



【思路二】

层次遍历


/*---------------------------------------
*   日期:2015-05-08
*   作者:SJF0115
*   题目: 129.Sum Root to Leaf Numbers
*   网址:https://leetcode.com/problems/sum-root-to-leaf-numbers/
*   结果:AC
*   来源:LeetCode
*   博客:
-----------------------------------------*/
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

// 二叉树节点
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    int sumNumbers(TreeNode* root) {
        if(root == nullptr){
            return 0;
        }//if
        queue<TreeNode*> nodeQueue;
        queue<int> sumQueue;
        nodeQueue.push(root);
        sumQueue.push(0);

        int curSum = 0;
        int totalSum = 0;
        TreeNode* node;
        // 层次遍历
        while(!nodeQueue.empty()){
            // 当前节点
            node = nodeQueue.front();
            nodeQueue.pop();
            // 当前路径和
            curSum = sumQueue.front();
            sumQueue.pop();
            curSum = curSum * 10 + node->val;
            // 左子结点
            if(node->left){
                nodeQueue.push(node->left);
                sumQueue.push(curSum);
            }//if
            // 右子结点
            if(node->right){
                nodeQueue.push(node->right);
                sumQueue.push(curSum);
            }//if
            // 叶子节点计算总和
            if(node->left == nullptr && node->right == nullptr){
                totalSum += curSum;
            }//if
        }//while
        return totalSum;
    }
};


层次遍历,对与每个节点都要记住父节点的当前和。因为计算每个节点的当前和都会因父节点而不一样。

到达叶子节点代表一条路径的结束。这个当前和加入到总和中。

【思路三】

先序遍历的非递归版本

/*---------------------------------------
*   日期:2015-05-08
*   作者:SJF0115
*   题目: 129.Sum Root to Leaf Numbers
*   网址:https://leetcode.com/problems/sum-root-to-leaf-numbers/
*   结果:AC
*   来源:LeetCode
*   博客:
-----------------------------------------*/
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
using namespace std;

// 二叉树节点
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    int sumNumbers(TreeNode* root) {
        if(root == nullptr){
            return 0;
        }//if
        stack<TreeNode*> nodeStack;
        nodeStack.push(root);
        stack<int> sumStack;
        sumStack.push(0);

        TreeNode* node;
        int curSum = 0;
        int totalSum = 0;
        // 先序遍历 非递归
        while(!nodeStack.empty()){
            // 当前节点
            node = nodeStack.top();
            nodeStack.pop();
            // 当前路径和
            curSum = sumStack.top();
            sumStack.pop();
            curSum = curSum * 10 + node->val;
            // 右子节点
            if(node->right){
                nodeStack.push(node->right);
                sumStack.push(curSum);
            }//if
            // 左子结点
            if(node->left){
                nodeStack.push(node->left);
                sumStack.push(curSum);
            }//if
            // 叶子节点计算总和
            if(node->left == nullptr && node->right == nullptr){
                totalSum += curSum;
            }//if
        }//while
        return totalSum;
    }
};


【温故】

/*---------------------------------------
*   日期:2015-05-08
*   作者:SJF0115
*   题目: 129.Sum Root to Leaf Numbers
*   网址:https://leetcode.com/problems/sum-root-to-leaf-numbers/
*   结果:AC
*   来源:LeetCode
*   博客:
-----------------------------------------*/
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

// 二叉树节点
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    int sumNumbers(TreeNode* root) {
        if(root == nullptr){
            return 0;
        }//if
        int curSum = 0;
        int totalSum = 0;
        helper(root,curSum,totalSum);
        return totalSum;
    }
private:
    void helper(TreeNode* root,int curSum,int &totalSum){
        if(root == nullptr){
            return;
        }//if
        // 先序遍历
        curSum = curSum * 10 + root->val;
        // 在叶子节点处计算总和
        if(root->left == nullptr && root->right == nullptr){
            totalSum += curSum;
            return;
        }//if
        // 左子树
        helper(root->left,curSum,totalSum);
        // 右子树
        helper(root->right,curSum,totalSum);
    }
};




目录
相关文章
|
8月前
|
存储 C++ Python
LeetCode刷题---Add Two Numbers(一)
LeetCode刷题---Add Two Numbers(一)
|
11月前
|
存储 算法 安全
LeetCode - #2 Add Two Numbers
我们社区从本期开始会将顾毅(Netflix 增长黑客,《iOS 面试之道》作者,ACE 职业健身教练。)的 Swift 算法题题解整理为文字版以方便大家学习与阅读。 不积跬步,无以至千里;不积小流,无以成江海,Swift社区 伴你前行。
LeetCode - #2 Add Two Numbers
LeetCode 1380. 矩阵中的幸运数 Lucky Numbers in a Matrix
LeetCode 1380. 矩阵中的幸运数 Lucky Numbers in a Matrix
LeetCode Contest 178-1365. 有多少小于当前数字的数字 How Many Numbers Are Smaller Than the Current Number
LeetCode Contest 178-1365. 有多少小于当前数字的数字 How Many Numbers Are Smaller Than the Current Number
LeetCode 5340. 统计有序矩阵中的负数 Count Negative Numbers in a Sorted Matrix
LeetCode 5340. 统计有序矩阵中的负数 Count Negative Numbers in a Sorted Matrix
LeetCode 357. Count Numbers with Unique Digits
给定一个非负整数 n,计算各位数字都不同的数字 x 的个数,其中 0 ≤ x < 10n 。
64 0
LeetCode 357. Count Numbers with Unique Digits
|
存储 Python
LeetCode 315. Count of Smaller Numbers After Self
给定一个整数数组 nums,按要求返回一个新数组 counts。数组 counts 有该性质: counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。
75 0
LeetCode 315. Count of Smaller Numbers After Self
|
存储
Leetcode-Medium 2. Add Two Numbers
Leetcode-Medium 2. Add Two Numbers
52 0
Leetcode-Easy 985. Sum of Even Numbers After Queries
Leetcode-Easy 985. Sum of Even Numbers After Queries
80 0
LeetCode解题之二:Add Two Numbers
LeetCode解题之二:Add Two Numbers