azl397985856 commented 3 years ago

129. 求根到叶子节点数字之和

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/sum-root-to-leaf-numbers/

前置知识

DFS
BFS

前序遍历

题目描述


给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。

例如，从根到叶子节点路径 1->2->3 代表数字 123。

计算从根到叶子节点生成的所有数字之和。

说明: 叶子节点是指没有子节点的节点。

示例 1:

输入: [1,2,3] 1 / \ 2 3 输出: 25 解释: 从根到叶子节点路径 1->2 代表数字 12. 从根到叶子节点路径 1->3 代表数字 13. 因此，数字总和 = 12 + 13 = 25. 示例 2:

输入: [4,9,0,5,1] 4 / \ 9 0 / \ 5 1 输出: 1026 解释: 从根到叶子节点路径 4->9->5 代表数字 495. 从根到叶子节点路径 4->9->1 代表数字 491. 从根到叶子节点路径 4->0 代表数字 40. 因此，数字总和 = 495 + 491 + 40 = 1026.

leungogogo commented 3 years ago

LC129. Sum Root to Leaf Numbers

Method. Recursive DFS

Main Idea

Use dfs to find all the root-to-leaf path numbers(use an integer s to record the number represented by previous nodes in the path, and newNum = s * 10 + root.val), and sum them up.

Code

class Solution {
    private int sum;
    public int sumNumbers(TreeNode root) {
        if (root == null) return 0;
        sum = 0;
        dfs(root, 0);
        return sum;
    }

    private void dfs(TreeNode root, int s) {
        if (root.left == null && root.right == null) {
            sum += (s * 10 + root.val);
            return;
        }

        // dfs
        if (root.left != null) dfs(root.left, s * 10 + root.val);
        if (root.right != null) dfs(root.right, s * 10 + root.val);
    }
}

Complexity Analysis

Time: O(n)

Space: O(h) = O(n)

Method 2. Iterative DFS

Main Idea

Use a stack to simulate the call stack and store information about parent nodes and the number it represents.

Code

class Solution {
    public int sumNumbers(TreeNode root) {
        if (root == null) return 0;
        Deque<Pair<TreeNode, Integer>> stack = new ArrayDeque<>();
        TreeNode cur = root;
        int sum = 0, curNum = 0;
        while (cur != null || !stack.isEmpty()) {
            while (!stack.isEmpty() && cur == null) {
                Pair<TreeNode, Integer> p = stack.pop();
                cur = p.getKey().right;
                curNum = p.getValue();
            }

            if (cur != null) {
                curNum = curNum * 10 + cur.val;
                if (cur.left == null && cur.right == null) sum += curNum;
                else stack.push(new Pair<>(cur, curNum));
                cur = cur.left;
            }
        }
        return sum;
    }
}

Complexity Analysis

Time: O(n)

Space: O(n)

wangzehan123 commented 3 years ago


/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int sumNumbers(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int res = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode top = queue.poll();
                if (top.left == null && top.right == null) {
                    res += top.val;
                    continue;
                }
                if (top.left != null) {
                    top.left.val = top.val * 10 + top.left.val;
                    queue.offer(top.left);
                }
                if (top.right != null) {
                    top.right.val = top.val * 10 + top.right.val;
                    queue.offer(top.right);
                }
            }
        }
        return res;
    }
}

复杂度分析

令 n 为数组长度。

时间复杂度：$O(n)$
空间复杂度：$O(n)$

BpointA commented 3 years ago

思路

bfs+哈希表。遇到叶子节点直接将其值并入答案，否则计算其左右非空结点对应的值，将其储存于哈希表中，并将该结点加入栈。

Python3代码

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def sumNumbers(self, root: TreeNode) -> int:
        if root==None:
            return 0
        stk=[root]

        val={}
        val[root]=root.val
        res=0
        while len(stk)>0:
            p=stk.pop()
            if p.left==None and p.right==None:
                res+=val[p]
            else:
                if p.left!=None:
                    stk.append(p.left)
                    val[p.left]=val[p]*10+p.left.val
                if p.right!=None:
                    stk.append(p.right)
                    val[p.right]=val[p]*10+p.right.val

        return res

复杂度

时间复杂度：O(n) ，bfs过程需变更所有结点

空间复杂度：O(n) ，需要建立长度为n的哈希表

yanglr commented 3 years ago

思路

dfs(先序遍历)

与LeetCode112类似, 可使用dfs(其实是先序遍历)解决。

用变量sum记录结果。对二叉树做先序遍历, 用string变量path记录每一条路径, 如果到达了叶子结点, 就可以把path转为数字后加到sum中, 否则就继续用dfs对左子树(左子树不为null时)和右子树(右子树不为null时)做同样的处理。

代码

实现语言: C++

class Solution {
private:
    int sum = 0;
    string pathStr;

public:
    int sumNumbers(TreeNode *root) {
        dfs(root);
        return sum;
    }

private:
    void dfs(TreeNode *root) {
        if (root == nullptr) return;

        pathStr.append(to_string(root->val));
        if (root->left == nullptr && root->right == nullptr)
            sum += stoi(pathStr);
        else
        {
            if (root->left != nullptr)
                dfs(root->left);
            if (root->right != nullptr)
                dfs(root->right);
        }
        pathStr.pop_back();
    }
};

代码已上传到: leetcode-ac/91algo daily - github.com

复杂度分析

时间复杂度：O(n)
空间复杂度：O(h)

mmboxmm commented 3 years ago

思路

死磕递归

代码

fun sumNumbers(root: TreeNode?) = helper(0, root)
fun helper(base: Int, root: TreeNode?): Int {
  if (root == null) return 0
  val value = base * 10 + root.value
  if (root.left == null && root.right == null) return value

  return helper(value, root.left) + helper(value, root.right)
}

复杂度

Time: O(n)
Space: O(h)

cicihou commented 3 years ago


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def sumNumbers(self, root: Optional[TreeNode]) -> int:
        def dfs(root, n):
            if not root:
                return 0
            if not root.left and not root.right:
                return n*10+root.val
            left = dfs(root.left, n*10+root.val)
            right = dfs(root.right, n*10+root.val)
            return left+right
        return dfs(root, 0)

RocJeMaintiendrai commented 3 years ago

题目

https://leetcode-cn.com/problems/sum-root-to-leaf-numbers/

思路

使用recursion，将当前root和当前的值传到下一层，如果root 为null则返回该条路径的值，如果没有左右子树则代表是叶子节点，然后将上一层传来的值 x 10 再加上当前root的值。

代码

class Solution {
    public int sumNumbers(TreeNode root) {
        return helper(root, 0);
    }

    private int helper(TreeNode root, int num) {
        if(root == null) return 0;
        if(root.left == null && root.right == null) {
            return num * 10 + root.val;
        }
        return helper(root.left, num * 10 + root.val) + helper(root.right, num * 10 + root.val);
    }
}

复杂度分析

时间复杂度

O(n)

空间复杂度

O(n)

ysy0707 commented 3 years ago

思路：递归

class Solution {
    public int sumNumbers(TreeNode root) {
        return dfs(root,0);
        //从根节点进入辅助方法
    }
    private int dfs(TreeNode root,int sum){
        if (root == null){
            return 0;
        }
        //终止的条件
        sum = sum * 10 + root.val;
        //计算走到当前节点时的值
        if (root.left == null && root.right == null)
            return sum;
        //如果走到了叶子节点，则说明得到了完整路径，返回这条路径的值
        return dfs(root.left, sum) + dfs(root.right, sum);
        //如果不是，就继续递归，向左右节点继续向下
    }
}

时间复杂度：O(N) 空间复杂度：O(N)

yj9676 commented 3 years ago

[TOC]

LC129 求根到叶子节点数字之和 [Medium]

Sum Root to Leaf Numbers

DFS
link

思路

使用DFS, 把每条从根到叶子结点的路径全找出来相加

Solution

class Solution {
    int sum;

    public int sumNumbers(TreeNode root) {
        sum = 0;
        addSum(root, 0);
        return sum;
    }

    void addSum(TreeNode root, int last){
        if (root == null) {
            return;
        }

        if (root.left == null && root.right == null){
            sum += last * 10 + root.val;
            return;
        }

        addSum(root.left, last * 10 + root.val);
        addSum(root.right, last * 10 + root.val);
    }

}

复杂度分析

时间复杂度 : O(N) N为树的节点数
空间复杂度 : O(h) h为树的高度

xj-yan commented 3 years ago

class Solution {
    public int sumNumbers(TreeNode root) {
        if (root == null) return 0;
        List<String> list = new ArrayList<>();
        dfs(root, list, new StringBuilder());
        int sum = 0;
        for (String str : list){
            sum += Integer.parseInt(str);
        }
        return sum;
    }

    private void dfs(TreeNode root, List<String> list, StringBuilder sb){
        if (root == null) return;

        sb.append(root.val + "");
        if (root.left == null && root.right == null){
            list.add(sb.toString());
        }else {
            dfs(root.left, list, sb);
            dfs(root.right, list, sb);
        }
        sb.setLength(sb.length() - 1);
    }
}

Time Complexity: O(n), Space Complexity: O(h)

comst007 commented 3 years ago

129. 求根节点到叶节点数字之和

思路

dfs

代码

C++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
private:
    typedef long long int LLI;
    LLI ans;
    void dfs(TreeNode* p, LLI res){
        if(!p -> left && !p -> right){
            ans += res * 10 + p -> val;
            return;
        }
        if(p -> left){
            dfs(p -> left, res * 10 + p ->val);
        }
        if( p -> right){
            dfs(p -> right, res * 10 + p -> val);
        }
    }
public:
    int sumNumbers(TreeNode* root) {
        if(!root) return 0;
        ans = 0;
        dfs(root,0);
        return ans;
    }
};

复杂度分析

n 为树的结点个数。

时间复杂度 $O(n)$
空间复杂度 $O(logn)$

pophy commented 3 years ago

思路

DFS找到叶节点并记录在path中
- 更新结果Res
back tracking

Java Code

class Solution { 
    int res = 0;
    public int sumNumbers(TreeNode root) {
        if (root == null) {
            return 0;
        }
        LinkedList<TreeNode> path = new LinkedList();
        dfs(root, path);
        return res;
    }  

    public void dfs(TreeNode root, LinkedList<TreeNode> path) {
        if (root == null) {
            return;
        }
        path.add(root);
        if (root.left == null && root.right == null) {
            int temp = 0;
            for (int i = 0; i<path.size(); i++) {
                temp = temp * 10 + path.get(i).val;
            }
            res += temp;
        } else {
            dfs(root.left, path);
            dfs(root.right, path);
        }
        path.removeLast();
    }

}

时间&空间

时间 O(n)
空间 O(h)

ivalkshfoeif commented 3 years ago

class Solution {
    int ans;
    public int sumNumbers(TreeNode root) {
        ans = 0;
        dfs(root,0);
        return ans;

    }
    private void dfs(TreeNode node, int num){
        if (node == null){
            return;
        }
        int new_num = num * 10 + node.val;
        if (node.left == null && node.right == null){
            ans += new_num;
            return;
        }
        if (node.left != null){
            dfs(node.left,new_num);
        }
        if (node.right != null){
            dfs(node.right, new_num);
        }
        return;
    }
}

DFS

a244629128 commented 3 years ago


var sumNumbers = function(root) {
   var traverse = function(root,prevSum){
       if(!root){
           return 0;
       }
       var currSum = prevSum*10 + root.val;
        if(!root.left && !root.right){
           return currSum;
       }
       return traverse(root.left,currSum) +  traverse(root.right,currSum) 

   }
   return traverse(root,0);
};
// time O(n)
//space O(n)

nonevsnull commented 3 years ago

思路

拿到题的直觉解法
- 树的问题都是遍历问题；
- 求路径问题，顺带求路径上的值的和；
- 可以把路径作为参数随函数带着，很方便；
- 节点的值，需要知道根的值作为基础，因此是个pre-order
- 题目要返回的总和，可以通过global，也可以通过return
  - global：total；递归为void，参数带了当前node之前的pathsum信息。更新当前node的score后往下传递，直到遇到左右都为null的叶子结点，更新total；
  - return：递归为total；遇到左右都为null的叶子结点，返回score；

AC

代码

//use global to save total
class Solution {
    int total;
    public int sumNumbers(TreeNode root) {
        preorder(root, 0);
        return total;
    }
    /*
        return: void；在递归过程中更新total；
        stop: root == null or leaf
        param: root, pathSum (before root)
    */
    public void preorder(TreeNode root, int pathscore){
        if(root == null){
            return;
        }

        int curPathScore = pathscore * 10 + root.val;

        if(root.left == null && root.right == null){
            total += curPathScore;
            return;
        }
        preorder(root.left, curPathScore);
        preorder(root.right, curPathScore);
    }
}

//use recusion return as total
class Solution {
    public int sumNumbers(TreeNode root) {
        return preorder(root, 0);
    }

    /*
        return: sum of leaf score which is pathsum, in this branch;
        stop: root == null or leaf
        param: root, pathSum (before root)
    */
    public int preorder(TreeNode root, int prepathSum){
        if(root == null) return 0;

        int curPathSum = prepathSum * 10 + root.val;

        if(root.left == null && root.right == null) return curPathSum;

        int left = preorder(root.left, curPathSum);
        int right = preorder(root.right, curPathSum);

        return left+right;
    }
}

复杂度

time: 每个节点都遍历到了，因此为O(N)。注意与递归无关。 space: 递归所需要的stack，要求O(logN)，亦即tree的高度;

erik7777777 commented 3 years ago

代码

int res = 0;
public int sumNumbers(TreeNode root) {
        calculate(root, 0);
        return res;
    }

    private void calculate(TreeNode root, int sum) {
        if (root == null) return;
        if (root.left == null && root.right == null) {
            res += sum * 10 + root.val;
            return;
        }
        calculate(root.left, sum * 10 + root.val);
        calculate(root.right, sum * 10 + root.val);
    }

复杂度 time O(n) -> n is # of nodes. space O(h) -> depth of stack -> longest path of the tree worst O(n), best O(logn)

yyangeee commented 3 years ago

129

https://leetcode-cn.com/problems/sum-root-to-leaf-numbers/

思路

官方题解https://leetcode-solution.cn/solutionDetail?type=3&id=15&max_id=2 dfs,递归的参数为左右节点及目前的和，叶节点前每一层都需要*10.跳出条件为左右节点都为空

语法

代码

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        def dfs(root,cur):
            if not root: return 0
            if not root.left and not root.right: return cur * 10 + root.val
            return dfs(root.left, cur * 10 + root.val) + dfs(root.right, cur * 10 + root.val)
        return dfs(root, 0)

复杂度

时间复杂度：$O(n)$
空间复杂度：$O(n)$

Menglin-l commented 3 years ago

思路：

1.子节点的数值等于自身节点值 + 父结点的值 * 10；

2.前序遍历，这里使用递归，到达叶子节点返回。

代码部分：

class Solution {
    public int sumNumbers(TreeNode root) {

        return sumNumbers(root, 0);
    }

    public int sumNumbers(TreeNode root, int number) {

        if (root == null) return 0;
        int n = root.val + number * 10;
        if (root.left == null && root.right == null) return n;

        return sumNumbers(root.left, n) + sumNumbers(root.right, n);

    }
}

复杂度：

Time: O(N)

Space: O(N)

yingliucreates commented 3 years ago

link:

https://leetcode.com/problems/sum-root-to-leaf-numbers/

代码 Javascript

const sumNumbers = function (root, current = 0) {
  if (root === null) return 0;
  let value = current * 10 + root.val;
  if (root.left === null && root.right === null) return value;
  return sumNumbers(root.left, value) + sumNumbers(root.right, value);
};

复杂度分析

空间时间都是 O(n)

fzzfgbw commented 3 years ago

思路

递归

代码

func sumNumbers(root *TreeNode) int {
    return dfsSum(root, 0)
}
func dfsSum(root *TreeNode, sum int) int {
    if root == nil {
        return 0
    } else{
        sum = sum*10+root.Val
        if root.Left == nil && root.Right == nil {
            return sum
        }else{
            return dfsSum(root.Left,sum)+dfsSum(root.Right,sum)
        }

    }
}

复杂度分析

时间复杂度：O(N)。
空间复杂度：O(h)。

falconruo commented 3 years ago

思路:

递归法（DFS）:前面值乘十加上现在节点的值再分别加上左右节点的值并返回

迭代法（BFS): 使用栈或队列存放左右子节点, 定义变量sum为leaf number的和。

复杂度分析:

时间复杂度: O(n), n为树的节点数
空间复杂度: DFS -> O(logn), 树的深度; BFS -> O(n)

代码(C++):

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

// 递归法（DFS）
class Solution {
public:
    int sumNumbers(TreeNode* root) {
        return dfs(root, 0);
    }
private:
    int dfs(TreeNode* node, int num) {
        if (!node) return 0;

        num = num * 10 + node->val;

        if (!node->left && !node->right)
            return num;

        return dfs(node->left, num) + dfs(node->right, num);
    }
};

// 迭代法（BFS)
class Solution {
public:
    int sumNumbers(TreeNode* root) {
        if (!root) return 0;

        queue<TreeNode*> q;
        q.push(root);

        int sum = 0;

        while (!q.empty()) {
            int size = q.size();
            while (size--) {
                TreeNode* cur = q.front();
                q.pop();
                if (cur->left) {
                    cur->left->val += cur->val*10; 
                    q.push(cur->left);
                }

                if (cur->right) {
                    cur->right->val += cur->val*10;
                    q.push(cur->right);
                }

                if (!cur->left && !cur->right) // leaf node -> found a path, add to sum
                    sum += cur->val;
            }
        }
        return sum;
    }
};

yachtcoder commented 3 years ago

Shift the numbers and add the new node's value until we reach the leaf layer.

class Solution:
    def sumNumbers(self, root: TreeNode) -> int:
        def dfs(node, n):
            if not node: return 0
            n = n*10 + node.val
            if not node.left and not node.right:
                return n
            return dfs(node.left, n) + dfs(node.right, n)
        return dfs(root, 0)

zhangzz2015 commented 3 years ago

思路

方法1，分析需要知道所有leaf节点到root的通路个数，每一条通路对应一个数，例如[4,9,0,5,1]。包含三条通路495 491 40。我们可分解为在 9的节点有两条通路到leaf为 95 91，在4的节点有3条到leaf，每条路径的长度不同，对于长度为2，4则变成400，长度为1，4则变成40。只要记录root到每个leaf路径长度，则在root，是收集所有的路径，每条路径增加root->val 10^长度。采用返回vector办法，记录当前 root 到所有leaf节点的长度，对于root需要收集左右子树的leaf节点，并增加1，合并后返回。时间复杂度为O(NM)，m为leaf的节点数，因为每次需要合并计算leaf的路径长度，空间复杂度为O(h*M)。
方法2，采用dfs的迭代解法，采用栈，记录从root到当前访问的节点对应的数，碰到leaf，则把数累加。时间复杂度为O(N)，空间复杂度为O(h)，为数的高度，最差的情况下为 O(N)。

关键点

代码

语言支持：C++

C++ Code:

class Solution {
public:
    int ret =0; 
    int sumNumbers(TreeNode* root) {

        if(root==NULL)
            return ret; 
        dfs(root);
        return ret; 

    }

    ///  return leaf level. 
    //    4 -->  9  0  --->  5 1     for root.  sum root->val * 10 ^ level  
    vector<int> dfs(TreeNode* root)
    {
        if(root->left ==NULL && root->right == NULL)
        {
            ret += root->val; 
            return {0}; 
        }
       vector<int> leftVec;
        if(root->left)
          leftVec= dfs(root->left); 
        vector<int> rightVec;
        if(root->right)
          rightVec= dfs(root->right); 
        vector<int> retVec; 
        for(int i =0; i< leftVec.size(); i++)
        {
            leftVec[i]++; 
            retVec.push_back(leftVec[i]); 
            ret += root->val * pow(10, leftVec[i]);
        }
        for(int i =0; i< rightVec.size(); i++)
        {
            rightVec[i]++; 
            retVec.push_back(rightVec[i]); 
            ret += root->val * pow(10, rightVec[i]);            
        }
        return retVec; 
    }
};

class Solution {
public:

    int sumNumbers(TreeNode* root) {

        int ret =0; 
        if(root==NULL)
            return ret; 
        vector<pair<TreeNode*,int>> stack; 
        stack.push_back(make_pair(root, root->val)); 
        while(stack.size())
        {
            pair<TreeNode*, int> current = stack.back(); 
            stack.pop_back();
            if(current.first->left==NULL && current.first->right==NULL)
            {
                ret += current.second; 
            }
            if(current.first->left)
            {
                stack.push_back(make_pair(current.first->left, current.second*10 + current.first->left->val)); 
            }
            if(current.first->right)
            {
                stack.push_back(make_pair(current.first->right, current.second*10 + current.first->right->val));                 
            }
        }

        return ret; 
    }
};

MonkofEast commented 3 years ago

129. Sum Root to Leaf Numbers

Click Me

Algo

path finding: DFS

remember to strike when None-Node & leaf-Node

inital val of currSum should be 0

Code

class Solution:
    def sumNumbers(self, root: Optional[TreeNode]) -> int:

        # find all the path, and return them in a sumed way     
        def dfs(root, currSum):
            # if curr node is None (depth==0), strike
            if not root: return 0
            # if reach out to a leaf (depth==1), strike
            if not root.left and not root.right: return currSum*10 + root.val

            # go on with left & right branched
            return dfs(root.left, currSum*10 + root.val) + dfs(root.right, currSum*10 + root.val)

        return dfs(root, 0)

Comp

T: O(N)

S: O(depth),

zjsuper commented 3 years ago

idea: DFS Time O(N)

class Solution:
    def sumNumbers(self, root: Optional[TreeNode]) -> int:

        return self.dfs(root,0)
    def dfs(self,root,cur):
        if not root:
            return 0
        if not root.left and not root.right:
            return cur * 10 + root.val
        return self.dfs(root.left,cur * 10 + root.val)+self.dfs(root.right,cur * 10 + root.val)

florenzliu commented 3 years ago

Explanation

Approach 1: recursion
- Write a helper function (node, currSum) to traverse the tree to find all the numbers from root to leaf
- Update currSum at each node
- When the node is leaf node, add currSum to the total sum
Approach 2: iteration
- Use a stack to store (node, currSum) at each node and DFS
- Update currSum at each node
- When the node is leaf node, add currSum to the total sum

Python

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

# Approach 1
class Solution:
    def sumNumbers(self, root: TreeNode) -> int:
        def helper(node, currSum):
            nonlocal s
            if node:
                currSum = currSum * 10 + node.val
                if not node.left and not node.right:
                    s += currSum
                helper(node.left, currSum)
                helper(node.right, currSum)
        s = 0
        helper(root, 0)
        return s

# Approach 2
class Solution:
    def sumNumbers(self, root: TreeNode) -> int:
        s = 0
        stack =[(root, 0)]
        while stack:
            node, currSum = stack.pop()
            if node:
                currSum = currSum * 10 + node.val
                if not node.left and not node.right:
                    s += currSum
                if node.left:
                    stack.append((node.left, currSum))
                if node.right:
                    stack.append((node.right, currSum))
        return s

Complexity

Time Complexity: O(N)
Space Complexity: O(H) where H is the height of the tree

asuka1h commented 3 years ago

思路: DFS 找到每一条从根到叶的路径, 在叶结点的时候把沿途加上的数字放在一个全局变量里 time O(N) class Solution { private: int sum = 0; int curr = 0; public: int sumNumbers(TreeNode root) { helper(root, 0); return sum; } void helper(TreeNode root, int curr){ if(root == nullptr){ return; } if(root ->left == nullptr && root->right == nullptr){ curr = curr * 10 + root->val; sum += curr; return; }

        helper(root-> left, curr * 10 +root->val);
       helper(root->right, curr* 10 +root->val);
}

};

leo173701 commented 3 years ago

思路要点： DFS 找到每一条路径，并且用数组记录下走过的每一个节点（或者节点的值），如果这个节点没有子节点，那就加入进res 中

'''python

class Solution: def sumNumbers(self, root: Optional[TreeNode]) -> int: res = 0

    path = [root.val]
    stack = [(root,[root.val],root.val)]
    while stack:

        cur, path, pathsum = stack.pop()

        if not cur.left and not cur.right:
            res +=(pathsum)
            # print(path)
        if cur.right:
            stack.append((cur.right,path+[cur.right.val], 10*pathsum + cur.right.val))
        if cur.left:
            stack.append((cur.left, path+[cur.left.val], 10*pathsum+ cur.left.val))
    return res

'''

thinkfurther commented 3 years ago

思路

dfs遍历所有分支

代码

class Solution:
    def sumNumbers(self, root: Optional[TreeNode]) -> int:
        return self.dfs(root, 0)        

    def dfs(self, node, val):
        if not node:
            return 0
        if not node.left and not node.right:
            return val * 10 + node.val

        return self.dfs(node.left, val * 10 + node.val) + self.dfs(node.right, val * 10 + node.val)

复杂度

时间复杂度：O(n)

空间复杂度：O(h)

q815101630 commented 3 years ago

Thought

这道题的思路就是先序遍历，basecase 是当遇到leaf 时候，我们就知道当前数字到底了，便return当前path 表示的数字。那么在上一层，便可以让当前两边 children 返回的值相加。因为我们没有加上当前层表示的值而是只加了他们children 表示的值，所以不会重复计算。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def sumNumbers(self, root: TreeNode) -> int:
        def recur(root, cur):
            if not root:
                return 0
            if not root.left and not root.right:
                return cur*10+root.val

            cur = cur*10+root.val
            left = recur(root.left, cur)
            right = recur(root.right, cur)
            return left+right

        return recur(root, 0)
'''
   1
   /\
2     3

'''

Time: O(n) 先序遍历 Space: O(h), h is the longest path

kidexp commented 3 years ago

thoughts

标准dfs，先序遍历，传从root到当前节点的path sum，当遍历到叶子结点加到最后的result里面

code

class Solution:
    def sumNumbers(self, root: Optional[TreeNode]) -> int:
        sum_ = 0

        def dfs(node, path_sum):
            nonlocal sum_
            if node:
                new_path_sum = path_sum * 10 + node.val
                if node.left:
                    dfs(node.left, new_path_sum)
                if node.right:
                    dfs(node.right, new_path_sum)
                if not node.left and not node.right:
                    sum_ += new_path_sum

        dfs(root, 0)
        return sum_

complexity

time O(n)

Space O(h) h是树的高度

heyqz commented 3 years ago

代码

class Solution:
    def sumNumbers(self, root: Optional[TreeNode]) -> int:

        def dfs(cur, num):
            if not cur:
                return 0
            num = num * 10 + cur.val
            if not cur.left and not cur.right:
                return num
            return dfs(cur.left, num) + dfs(cur.right, num)

        return dfs(root, 0)

复杂度

时间复杂度 O(n) 空间复杂度 O(h), h: 二叉树的高度

AgathaWang commented 3 years ago

#dfs
#python
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def sumNumbers(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        # DFS
        def dfs(root,prevtotal): # cur is the current sum
            if not root:
                return 0
            if not root.left and not root.right:
                return 10*prevtotal + root.val
            return dfs(root.left,root.val+10*prevtotal) + dfs(root.right,root.val+10*prevtotal)
        return dfs(root,0)

time complex: O(N)

ghost commented 3 years ago

题目

Sum Root to Leaf Numbers

思路

DFS

代码

class Solution:
    def sumNumbers(self, root: Optional[TreeNode]) -> int:
        return self.helper(root, 0)

    def helper(self, node, num):
        if not node: return 0
        if not node.left and not node.right: return num * 10 + node.val
        return self.helper(node.left, num * 10 + node.val) + self.helper(node.right, num * 10 + node.val)

复杂度

Space: O(N) Time: O(N)

tongxw commented 3 years ago

思路

显然用dfs求解更方便一些。 dfs遍历时带着上次计算好的总和。如果是空节点就返回0。总和是上面的父节点计算结果，所以先乘10，并加上当前节点值。如果是叶子节点就可以返回了。如果不是，就继续向下遍历。

代码

/**
 * @param {TreeNode} root
 * @return {number}
 */
var sumNumbers = function(root) {
    function dfs(root, total) {
      if (root == null) {
        return 0;
      }

      total = total * 10 + root.val;
      if (!root.left && !root.right) {
        return total;
      } else {
        return dfs(root.left, total) + dfs(root.right, total);
      }
    }

    return dfs(root, 0);
};

TC: O(n)
SC: O(h)

zol013 commented 3 years ago

思路：用了后序遍历，比较麻烦 dfs每次返回当前节点到它下面叶节点的和以及节点高度

class Solution:
    def sumNumbers(self, root: Optional[TreeNode]) -> int:
        sums = self.dfs(root)
        ans = 0
        for num, ht in sums:
            ans += num
        return ans
    def dfs(self, node):
        if not node: return
        if not node.left and not node.right:
            return [(node.val, 0)]
        leftvals = []
        rightvals = []
        if node.left:
            leftvals = self.dfs(node.left)     
        if node.right:
            rightvals = self.dfs(node.right)  
        curvals = []
        for num, ht in leftvals + rightvals:
            curnum = node.val * 10**(ht + 1) + num
            curvals.append((curnum, ht + 1))
        return curvals

Time Complexity: O(n) Space Complexity: O(n)

ginnydyy commented 3 years ago

Problem

https://leetcode.com/problems/sum-root-to-leaf-numbers/

Notes

DFS + recursion
- need to use a class variable to record sum.
- helper method has the parent node's value last, so each node can update its value by doing last * 10 + curr.val.
- when the current node is a leaf node, update the sum.
- when the current node has left/right child, pass the updated last value and call helper method for left/right child recursively.
BFS
- use a queue to support BFS
- when the current node (the one just polled from the queue) is a leaf node, add its value to sum.
- when the current node has left/right child, update the left/right value using curr.val * 10 + curr.left/curr.val * 10 + curr.right, so the child node's value will be updated and offered to the queue.

Solution

DFS + recursion

// DFS
class Solution {
int sum = 0;
public int sumNumbers(TreeNode root) {
    helper(root, 0);
    return sum;
}

private void helper(TreeNode node, int last){
    if(node == null){
        return;
    }
    if(node.left == null && node.right == null){
        sum += last * 10 + node.val;
    }
    if(node.left != null){
        helper(node.left, last * 10 + node.val);
    }
    if(node.right != null){
        helper(node.right, last * 10 + node.val);
    }
}
}

BFS

// BFS
class Solution {
public int sumNumbers(TreeNode root) {
    int sum = 0;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while(!queue.isEmpty()){
        TreeNode node = queue.poll();
        if(node.left == null && node.right == null){
            sum += node.val;
        }
        if(node.left != null){
            node.left.val += node.val * 10;
            queue.offer(node.left);
        }
        if(node.right != null){
            node.right.val += node.val * 10;
            queue.offer(node.right);
        }
    }
    return sum;
}
}

Complexity

DFS + recursion
- Time: O(n) to scan each node (n is the number of tree nodes).
- Space: O(h) for recursion (h is the height of the tree, best case h is logn, worst case h is n).
BFS
- Time: O(n) to scan each node.
- Space: O(k) for the queue (k is the number of nodes in the queue, worst case k is n/2).

banjingking commented 3 years ago

思路

DFS

代码

public class Solution {
    public int sumNumbers(TreeNode root) {
        return sumNumbers(root, 0);
    }

    private int sumNumbers(TreeNode root, int sum){
        if(root == null) return 0;
        if(root.left == null && root.right == null)
            return sum + root.val;

        return sumNumbers(root.left, (sum + root.val) * 10) + sumNumbers(root.right, (sum + root.val) * 10);

    }
}

HackBL commented 3 years ago

DFS

class Solution {
public int sumNumbers(TreeNode root) {
    return sumNumbers(root, 0);
}

public int sumNumbers(TreeNode root, int sum) {
    if (root == null) return 0;

    if (root.left == null && root.right == null) {
        return sum * 10 + root.val;
    }

    return sumNumbers(root.left, sum*10+root.val) + sumNumbers(root.right, sum*10+root.val);
}
}

Time: O(n)
Space: O(logn)

BFS

class Solution {
public int sumNumbers(TreeNode root) {
    if (root == null) return 0;
    int sum = 0;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);

    while (!queue.isEmpty()) {
        root = queue.poll();

        if (root.left == null && root.right == null) {
            sum += root.val;
        }

        if (root.left != null) {
            root.left.val += root.val*10;
            queue.offer(root.left);
        }

        if (root.right != null) {
            root.right.val += root.val*10;
            queue.offer(root.right);
        }
    }        

    return sum;
}
}

Time: O(n)
Space: O(n)

Zhang6260 commented 3 years ago

JAVA版本

思路：就进行深度优先遍历，需要注意的是结束条件是当前节点是叶子节点，（如果是非空的话可能会重复计算。）

class Solution {

public int sumNumbers(TreeNode root) {

if(root==null)return 0;

return fun(root,0);

}

public int fun(TreeNode root,int temp){

if(root.left==null&&root.right==null)return temp*10+root.val;

temp=temp*10+root.val;

if(root.left==null)return fun(root.right,temp);

if(root.right==null)return fun(root.left,temp);

return fun(root.left,temp)+fun(root.right,temp);

}

}

时间复杂度：O(n)

空间复杂度：O(h)

biancaone commented 3 years ago

思路 🏷️

DFS

代码 📜

class Solution:
    def sumNumbers(self, root: TreeNode) -> int:
        if  not root:
            return 0
        return self.helper(root, 0)

    def helper(self, root, sum):
        if not root:
            return 0
        sum = sum * 10 + root.val 

        if not root.left and not root.right:
            return sum

        left = self.helper(root.left, sum)
        right = self.helper(root.right, sum)

        return left + right

复杂度 📦

时间复杂度 O(n)
空间复杂度O(1)

okbug commented 3 years ago

思路

DFS 每次递归子节点的时候都把当前的v传递，走到叶子结点的时候就把结果加上当前的值

代码

C++

class Solution {
public:
    int result = 0;
    int sumNumbers(TreeNode* root) {
        if (root) dfs(root, 0);
        return result;
    }

    void dfs(TreeNode* root, int n) {
        n = n * 10 + root->val;
        if (!root->left && !root->right) result += n;
        if (root->left) dfs(root->left, n);
        if (root->right) dfs(root->right, n);
    }
};

JavaScript

var sumNumbers = function(root) {
    let sum = 0;
    if (!root) return 0;
    dfs(root, 0);
    function dfs({left, right, val}, n) {
        let v = n * 10 + val;
        if (!left && !right) sum += v;
        left && dfs(left, v);
        right && dfs(right, v);
    }

    return sum;
};

BlueRui commented 3 years ago

Problem 129. Sum Root to Leaf Numbers

Algorithm

Use DFS to recursively go down the tree to leaf values.
Pass the path sum from root to current node to DFS and return the root-to-leaf sum of all leafs of current node.

Complexity

Time Complexity: O(N) where N is the total number of nodes.
Space Complexity: O(h) where h is the height of the tree.

Code

Language: Java

public int sumNumbers(TreeNode root) {
    return dfs(root, 0);
}

private int dfs(TreeNode root, int number) {
    if (root == null) return number;
    number = number * 10 + root.val;
    if (root.left == null && root.right == null) {
        return number;
    }
    int leftSum = root.left == null ? 0 : dfs(root.left, number);
    int rightSum = root.right == null ? 0 : dfs(root.right, number);
    return leftSum + rightSum;
}

potatoMa commented 3 years ago

思路

DFS、BFS

代码

JavaScript Code

DFS

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var sumNumbers = function(root) {
    let res = 0;
    function trav(node, temp) {
        temp = `${temp}${node.val}`;
        if (node.left) trav(node.left, temp);
        if (node.right) trav(node.right, temp);
        if (!node.left && !node.right) {
            res += Number(temp);
        }
    }
    trav(root, '');
    return res;
};

BFS

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var sumNumbers = function(root) {
    let res = 0;
    const nodeStack = [root];
    const numStack = [root.val];
    while (nodeStack.length) {
        const curNode = nodeStack.shift();
        const curNum = numStack.shift();
        const { left, right } = curNode;
        if (left) {
            nodeStack.push(left);
            numStack.push(curNum * 10 + left.val);
        }
        if (right) {
            nodeStack.push(right);
            numStack.push(curNum * 10 + right.val);
        }
        if (!left && !right) {
            res += curNum;
        }
    }
    return res;
};

复杂度分析

时间复杂度：DFS BFS均为O(N)

空间复杂度：DFS为O(Height) (最坏的情况为O(N)) BFS为O(N)

hizhisong commented 3 years ago

DFS

// DFS
// 通过参数sum 递 进去直到叶子(递归终点)，归通过return加和处理后 归 回去
class Solution {
public:
    // 每往下一层，之前的sum*10
    int dfs(TreeNode* root, int sum) {
        // End
        if (root == nullptr) {
            return 0;
        }

        // 先序遍历 -- sum的每层加和
        // Calculate
        sum = sum*10 + root->val;

        // End
        if (root->left == nullptr && root->right == nullptr) {
            return sum;
        }

        // 在左右两边遍历完后，return，这个return属于后序遍历
        return dfs(root->left, sum) + dfs(root->right, sum);
    }

    int sumNumbers(TreeNode* root) {
        return dfs(root, 0);
    }
};

LOVEwitch commented 3 years ago

//dfs /**

Definition for a binary tree node.
function TreeNode(val, left, right) {
this.val = (val===undefined ? 0 : val)
this.left = (left===undefined ? null : left)
this.right = (right===undefined ? null : right)
} */ /**
@param {TreeNode} root
@return {number} */ var sumNumbers = function(root) { //递归 let num = '', sum = 0;

return dfs(root, 0);

}; var dfs = function(root, prevSum){ if(root === null) return 0; const sum = prevSum *10 +root.val if(root.left === null && root.right === null) { return sum; } else { return dfs(root.left, sum) + dfs(root.right, sum) } } //bfs /**

Definition for a binary tree node.
function TreeNode(val, left, right) {
this.val = (val===undefined ? 0 : val)
this.left = (left===undefined ? null : left)
this.right = (right===undefined ? null : right)
} */ /**
@param {TreeNode} root
@return {number} / var sumNumbers = function(root) { //广度优先 if(root === null) return 0; let sum = 0; const nodeQueue = [], numQueue = []; nodeQueue.push(root); numQueue.push(root.val); while(nodeQueue.length){ const currentNode = nodeQueue.shift(); const currentNum = numQueue.shift(); // sum += currentNum; // const left = currentNum 10 + currentNum; // const right = currentNum 10 + currentNum; if(currentNode.left === null && currentNode.right === null){ sum += currentNum; } else { if(currentNode.left !== null){ nodeQueue.push(currentNode.left); numQueue.push(currentNum 10 + currentNode.left.val) } if(currentNode.right !== null){ nodeQueue.push(currentNode.right); numQueue.push(currentNum * 10 +currentNode.right.val) } } } return sum;

};

maxyzli commented 3 years ago

// DFS
class Solution {
public:
    // 每往下一层，之前的sum*10
    int dfs(TreeNode* root, int sum) {
        // End
        if (root == nullptr) {
            return 0;
        }

        // 先序遍历 -- sum的每层加和
        // Calculate
        sum = sum*10 + root->val;

        // End
        if (root->left == nullptr && root->right == nullptr) {
            return sum;
        }

        // 在左右两边遍历完后，return，这个return属于后序遍历
        return dfs(root->left, sum) + dfs(root->right, sum);
    }

    int sumNumbers(TreeNode* root) {
        return dfs(root, 0);
    }
};

xingkong1994 commented 3 years ago

思路

采用DFS

代码

class Solution {
public:
    int sumNumbers(TreeNode* root) {
        if (!root)  return 0;
        int sum = 0;
        int count = 0;
        func(root, sum, count);
        return sum;
    }
    void func(TreeNode* node, int& sum, int count) {
        if (!node) return;
        if (!node->left && !node->right) {
            count = 10 * count + node->val;
            sum += count;
            return;
        }
        func(node->left, sum, 10 * count + node->val);
        func(node->right, sum, 10 * count + node->val);
        return;
    }
};

yan0327 commented 3 years ago

思路：又是没想到的一波=-= 关键还是DFS，以及叶子节点的判断。

func sumNumbers(root *TreeNode) int {
    return helper(root, 0)
}

func helper(root *TreeNode, cur int) int{
    if root == nil{
        return 0
    }
    cur = 10*cur + root.Val
    if root.Left == nil && root.Right == nil{
        return cur
    }
    return helper(root.Left, cur) + helper(root.Right, cur)
}

时间复杂度：O(n) 空间复杂度：O(n)

JiangyanLiNEU commented 3 years ago

Idea

DFS to visit all the node
String to hold the node value that we need

add int(string) to result when there is not more node in this branch

Implement (Runtim=O(n) Space=O(1))

class Solution(object):
def sumNumbers(self, root):
    def check(cur, tree, result):
        if not tree:
            return result+(int(cur))
        else:
            cur += str(tree.val)
            if not tree.left and not tree.right:
                result += (int(cur))
            if tree.left:
                result = check(cur, tree.left, result)
            if tree.right:
                result = check(cur, tree.right, result)
            return result
    if not root:
        return 0
    else:
        cur = str(root.val)
        result = 0
        if not root.left and not root.right:
            return int(cur)
        if root.left:
            result = check(cur, root.left, result)
        if root.right:
            result = check(cur, root.right, result)
        return result

leetcode-pp / 91alg-5-daily-check

【Day 15 】2021-09-24 - 129. 求根到叶子节点数字之和 #30

129. 求根到叶子节点数字之和

入选理由

题目地址

前置知识

题目描述

LC129. Sum Root to Leaf Numbers

Method. Recursive DFS

Main Idea

Code

Complexity Analysis

Method 2. Iterative DFS

Main Idea

Code

Complexity Analysis

思路

Python3代码

复杂度

思路

dfs(先序遍历)

代码

实现语言: C++

复杂度分析

思路

代码

复杂度

题目

思路

代码

复杂度分析

时间复杂度

空间复杂度

LC129 求根到叶子节点数字之和 [Medium]

link

思路

Solution

129. 求根节点到叶节点数字之和

思路

代码

复杂度分析

思路

Java Code

时间&空间

思路

代码

复杂度

代码

复杂度 time O(n) -> n is # of nodes. space O(h) -> depth of stack -> longest path of the tree worst O(n), best O(logn)

129

思路

语法

代码

复杂度

思路：

1.子节点的数值等于自身节点值 + 父结点的值 * 10；

2.前序遍历，这里使用递归，到达叶子节点返回。

代码部分：

复杂度：

Time: O(N)

Space: O(N)

link:

代码 Javascript

复杂度分析

思路

代码

思路

关键点

代码

129. Sum Root to Leaf Numbers

Algo

Code

Comp

T: O(N)

S: O(depth),

思路

代码

复杂度

Thought

thoughts