【Day 15 】2021-12-26 - 129. 求根到叶子节点数字之和

[azl397985856]

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.

[yan0327]

思路： 前序遍历+扩展参数 【扩展一个临界值】 dfs遍历：输入为root 和 num【根节点到该节点的数值总和】 1.判断节点是否为nil 2. num += root.Val 3.若是叶子节点，则直接加到输出out 4.dfs左右叶子节点

func sumNumbers(root *TreeNode) int {
    out := 0
    var dfs func(root *TreeNode,num int)
    dfs = func(root *TreeNode,num int){
        if root == nil{
            return
        }
        num += root.Val
        if root.Left == nil && root.Right == nil{
            out += num
            return
        }
        dfs(root.Left,num*10)
        dfs(root.Right,num*10)
    }
    dfs(root,0)
    return out
}

时间复杂度 O（n） 空间复杂度O（h）

[BpointA]

思路

DFS

JAVA代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int sumNumbers(TreeNode root) {
        if(root==null)
        {
            return 0;
        }
        int ans=0;
        Stack<TreeNode> stk=new Stack();
        Stack<Integer> vals=new Stack(); 
        stk.push(root);
        vals.push(root.val);
        while(stk.size()>0)
        {
            TreeNode p=stk.pop();
            int v=vals.pop();
            if(p.left==null && p.right==null)
            {
                ans+=v;
            }
            if(p.left!=null)
            {
                stk.push(p.left);
                vals.push(v*10+p.left.val);
            }
            if(p.right!=null)
            {
                stk.push(p.right);
                vals.push(v*10+p.right.val);
            }
        }
        return ans;

    }
}

[frgthyju]

使用DFS，依次对比树的根节点、左子树和右子树

func isSameTree(p *TreeNode, q *TreeNode) bool {
    if (p == nil && q == nil) {
        return true
    }
    if p == nil || q == nil{
        return false
    }
    if p.Val == q.Val{
        return isSameTree(p.Left,q.Left) && isSameTree(p.Right,q.Right)
    }
    return false
}

时间复杂度：O(min(m,n))两棵树最小的节点数

空间复杂度：O(min(heightP,heightQ))两棵树的最小高度，而最差情况下节点数等于高度，即O(min(m,n))

[Alexno1no2]

# 特例处理：root为空返回0
# 递归包含两个参数，当前节点node和从根到当前节点为止的十进制数num
# 当左节点存在，进入左节点的递归；当node的右节点存在，进入右节点的递归
# 当当前节点是叶子节点，直接把num加到结果中
# 返回结果

class Solution:
    def sumNumbers(self, root: TreeNode) -> int:
        self.res = 0
        if root is None:
            return self.res

        self.dfs(root,root.val)
        return self.res

    def dfs(self,node,num):
            if not node.left and not node.right:
                self.res += num
            if node.left:
                self.dfs(node.left, num * 10 + node.left.val)
            if node.right:
                self.dfs(node.right, num * 10 + node.right.val)

[wxj783428795]

思路

1. 遍历每个节点，如果节点存在，则用当前值+前一个值*10
2. 如果当前节点不存在任何子节点，则直接返回计算后的值
3. 如果存在任一左右子节点，则递归计算。

代码

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

var dfs = function (node, preSum) {
    if (!node) {
        return 0;
    }
    let sum = preSum * 10 + node.val;
    if (!node.left && !node.right) {
        return sum
    } else {
        return dfs(node.left, sum) + dfs(node.right, sum)
    }
}

复杂度分析

复杂度分析不是很会，不一定对，如果有错，请指正。

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

[CodeWithIris]

Question

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

Note (DFS)

• The traversal starts at the root node and computes the current number when a child node is encountered:
                                                  num = num*10 + node->val

• Use Depth-First-Search and the exit of the recursion is that the left and right nodes do not exist.

Solution (C++)

class Solution {
public:
    void dfs(TreeNode* node, int num, int& ans){
        if(node == nullptr) return;
        num = num*10 + node->val;
        if(node->left == nullptr && node->right == nullptr){
            ans += num;
            return ;
        }
        dfs(node->left, num, ans);
        dfs(node->right, num, ans);
    }
    int sumNumbers(TreeNode* root) {
        int ans = 0;
        dfs(root, 0, ans);
        return ans;
    }
};

Complexity

• T: O(n): All the nodes of this tree will be traversed over.
• S: O(n): The space complexity is the O(Depth of this tree). However, the worst situation is that the depth is equal to the number of nodes.

[feifan-bai]

思路

1. DFS 从根节点开始，遍历每个节点
2. 如果遇到叶子节点，将叶子节点val加到数字之和

3. 如果当前节点不是叶子节点，则计算数字，对子节点递归 代码

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

   复杂度分析

   • 时间复杂度：O(N), N = 节点数
   • 空间复杂度：O(N), N = 节点数

[charlestang]

思路

深度优先遍历树，找到每个根到叶子的路径生成数字。

代码

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

        def dfs(root: TreeNode, n: List[int]):
            if not root.left and not root.right:
                num = 0
                for a in n:
                    num = num * 10 + a
                nums.append(num * 10 + root.val)
            else:
                if root.left:
                    dfs(root.left, n + [root.val])
                if root.right:
                    dfs(root.right, n + [root.val])
        dfs(root, [])
        return sum(nums)

时间复杂度 O(n) 每个节点访问一次。

空间复杂度 O(n)

[li65943930]

function sumNumbers(root) { let sum = 0; let curLevel = []; if (root) { curLevel.push(root); } while (curLevel.length) { let nextLevel = []; for (let i = 0; i < curLevel.length; i++) { let cur = curLevel[i]; if (cur.left) { cur.left.val = cur.val 10 + cur.left.val; nextLevel.push(cur.left); } if (cur.right) { cur.right.val = cur.val 10 + cur.right.val; nextLevel.push(cur.right); } if (!cur.left && !cur.right) { sum += cur.val; } curLevel = nextLevel; } } return sum; }

[JudyZhou95]

思路

用dfs，每次把当前node的val和carry on结合成新的数字。到了叶节点(no left and no right) 就把当前数字加到res上。

代码

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

def dfs(self, node, carry):

    if node.left:
        self.dfs(node.left, carry*10+node.left.val)

    if node.right:            
        self.dfs(node.right, carry*10+node.right.val)

    if not (node.left or node.right):
        self.res += carry

复杂度

TC: O(N)

SC: O(H)

[Menglin-l]

approach: recursive preorder traversal

1. update the pathSum in each level

2. do the recursive calls until reaching the leaf node

3. update the sum

4. repeat the step 1 to 3 for the right child nodes

---

code:

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

    private void dfs(TreeNode root, int pathSum) {
        if (root == null) return;

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

        dfs(root.left, pathSum);
        dfs(root.right, pathSum);
    }
}

---

complexity:

Time: O(N), the number of nodes

Space: O(H), the height of the tree

[yijing-wu]

思路

DFS

代码

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

    public int dfs(TreeNode root, int prevSum) {
        if (root == null) {
            return 0;
        }
        int sum = prevSum * 10 + root.val;
        if (root.left == null && root.right == null) {
            return sum;
        } else {
            return dfs(root.left, sum) + dfs(root.right, sum);
        }
    }
}

复杂度分析

• Time Complexitty = O(N)
• Space Complexitty = O(N)

[laofuWF]

# pre order traversal
# use curr_sum to track the sum built at curr node
# 4 cases for each node:
# - Null: return -1 as a flag
# - Leaf: return left_sum + right_sum
# - node with only left child: return right_sum
# - node with only right child: return left_sum

# time: O(N)
# space: O(H)
class Solution:
    def sumNumbers(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0

        return self.pre_order(root, 0)

    def pre_order(self, node, curr_sum):
        if not node:
            return -1

        curr_sum = curr_sum * 10 + node.val
        left_sum = self.pre_order(node.left, curr_sum)
        right_sum = self.pre_order(node.right, curr_sum)

        # leaf node
        if left_sum == -1 and right_sum == -1:
            return curr_sum

        if left_sum == -1:
            return right_sum
        elif right_sum == -1:
            return left_sum

        return left_sum + right_sum

[wangzehan123]

代码

• 语言支持：Java

Java Code:

/**
 * 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;
    }
}

[CoreJa]

思路

• naive dfs思路：模拟测试写出来的。每次深搜的时候把目前的结果传递下去即可
• dfs思路：上面方法的优化。主要是代码更简洁了。
• bfs思路：经典层序遍历。把node和当前结果作为tuple放在队列里，到子节点再计入ans即可。

代码

class Solution:
    # naive dfs思路：模拟测试写出来的。每次深搜的时候把目前的结果传递下去即可
    def sumNumbers1(self, root: TreeNode) -> int:
        def dfs(root, num):
            if not root.left and not root.right:
                return root.val + num
            sum = 0
            if root.left:
                sum += dfs(root.left, root.val * 10 + num * 10)
            if root.right:
                sum += dfs(root.right, root.val * 10 + num * 10)
            return sum

        return dfs(root, 0)

    # dfs思路：上面方法的优化。主要是代码更简洁了。
    def sumNumbers2(self, root: TreeNode) -> int:
        def dfs(root, num):
            if not root:
                return 0
            if not root.left and not root.right:
                return root.val + 10 * num
            return dfs(root.left, root.val + num * 10) + dfs(root.right, root.val + num * 10)

        return dfs(root, 0)

    # bfs思路：经典层序遍历。把node和当前结果作为tuple放在队列里，到子节点再计入ans即可。
    def sumNumbers(self, root: TreeNode) -> int:
        ans = 0
        q = deque()
        q.append((root, 0))
        while q:
            node, cur = q.popleft()
            cur += node.val
            if node.left:
                q.append((node.left, cur * 10))
            if node.right:
                q.append((node.right, cur * 10))
            if not node.left and not node.right:
                ans += cur
        return ans

[xj-yan]

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

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

[Yachen-Guo]

思路

深度优先搜索，将上一层所得到的结果进位（presum*10）并和当前node的值相加

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int sumNumbers(TreeNode root) {
        return sumRec(root,0);
    }

    private int sumRec(TreeNode node, int preSum){
        if(node == null) return 0;
        int sum = 10*preSum + node.val;
        if(node.left == null && node.right == null){
            return sum;
        } 
        return sumRec(node.left,sum)+sumRec(node.right,sum);
    }
}

[zhangzz2015]

思路

• 分析当前节点数值和上一层相关，val = prevVal*10 + currentVal。因此采用前序遍历，当为leaf 节点时，把数sum起来。时间复杂度为O(N)，空间复杂度为O(N)，为递归的深度。

  关键点

代码

• 语言支持：C++

C++ Code:

/**
 * 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 {
public:
    int sumNumbers(TreeNode* root) {

        int ret =0; 
        dfs(root, 0, ret); 
        return ret; 
    }

    void dfs(TreeNode* root, int val, int& ret)
    {
        if(root==NULL)
            return; 
        int currentVal = val*10 + root->val; 
        if(root->left == NULL && root->right==NULL)
        {
             ret += (currentVal);
             return ; 
        }

        dfs(root->left, currentVal, ret); 
        dfs(root->right, currentVal, ret); 
    }
};

[callmeerika]

思路

利用递归，传下去的数字每次乘10

代码

 var countTree = function(p, num) {
        if(!p) return 0;
        if(!p.left&&!p.right) {
             return num*10 + p.val;
        }
        return countTree(p.left,num*10 + p.val) + countTree(p.right,num*10 + p.val) 
    };
var sumNumbers = function(root) {
    return countTree(root,0)
};

复杂度

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

[zwmanman]

思路

1. iterate until leaf node and calculate the sum on that path
2. calculate left and right sum of that node

代码

（此处撰写代码）

class Solution(object):
    def sumNumbers(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """

        return self.dfs(root, 0)

    def dfs(self, root, curr):
        if not root:
            return 0

        curr = curr * 10 + root.val

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

        l = self.dfs(root.left, curr)
        r = self.dfs(root.right, curr)

        return l + r

复杂度分析

• 时间复杂度：O(N)，其中 N 为Node个数。
• 空间复杂度：O(1)

[Tao-Mao]

Idea

Recursion and always return the sum.

Code

class Solution {
    public int sumNumbers(TreeNode root) {
        if (root == null) return 0;
        return helper(root, root.val);
    }

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

Complexity

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

[ZacheryCao]

Idea

DFS. Preorder scan the tree. The dfs function holds two inputs, current node and the number built by previuos step (pre). The termination condition is the node is leaf node or None. If the node is leaf node, we update pre to 10 pre + node.val. In other conditions, we also update pre to 10 pre + node.val and update the node to its left/right child

Code

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

Complexity

Time: O(N). dfs needs to scan all nodes Space: O(H). H: the height of the tree.

[ZacheryCao]

Idea

BFS. Scan the tree layer by layer and construct the number accordingly. Store both the node and the constructed number at current position. When the current node is the leaf node, add the number to the ans.

Code

class Solution:
    def sumNumbers(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        ans = 0
        stack = collections.deque()
        stack.append((root, root.val))
        while stack:
            node, val = stack.popleft()
            if not node.left and not node.right:
                ans += val
            if node.left:
                stack.append((node.left, val * 10 + node.left.val))
            if node.right:
                stack.append((node.right, val * 10 + node.right.val))
        return ans

Complexity:

Time: O(N) Space: O(W). The largest width of the tree.

[yingliucreates]

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);
};

[moirobinzhang]

def sumNumbers(self, root: Optional[TreeNode]) -> 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)

[Husky-Gong]

Code

class Solution {
    int result = 0;
    int curr = 0;
    public int sumNumbers(TreeNode root) {
        if (root == null) {
            return result;
        }

        curr = curr * 10 + root.val;

        if (root.left == null && root.right == null) {
            result += curr;
        } else {
            sumNumbers(root.left);
            if (root.left != null) {
                curr /= 10;
            }
            sumNumbers(root.right);
            if (root.right != null) {
                curr /= 10;
            }
        }
        return result;
    }
}

Complexity

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

[kandejiandefeng]

解题思路 定义一个数组来收集所有的值； 使用前序遍历 把所有的值相加

/**
 * 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 path = [];
    const DFS = (root, sum) => {
        if (root == null) return;
        if (root.left == null && root.right == null) {
            sum = sum * 10 + root.val;
            path.push(sum);
        }
        sum = sum * 10 + root.val;
        DFS(root.left, sum);
        DFS(root.right, sum);
    }
    DFS(root, 0);
    return path.reduce((prev, next) => {
        return prev + next;
    }, 0);
};

[HZGwebgit]

解题思路

使用DFS，依次对比树的根节点、左子树和右子树

代码

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

var dfs = function (node, preSum) {
    if (!node) {
        return 0;
    }
    let sum = preSum * 10 + node.val;
    if (!node.left && !node.right) {
        return sum
    } else {
        return dfs(node.left, sum) + dfs(node.right, sum)
    }
}

复杂度

时间复杂度：o(n)

[falconruo]

思路: 方法一、递归法（DFS） 方法二、迭代法(BFS)

复杂度分析:

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

代码(C++):

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);
    }
};

class Solution {
public:
    int sumNumbers(TreeNode* root) {
        queue<TreeNode*> qt;
        qt.push(root);

        int sum = 0;
        while (!qt.empty()) {
            size_t size = qt.size();
            while (size--) {
                TreeNode* cur = qt.front();
                qt.pop();

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

                if (!cur->left && !cur->right) sum += cur->val;
            }
        }

        return sum;
    }
};

[nonevsnull]

思路

//s6

• 思路与解法

• Tree主要看遍历，DFS主要看写法；BFS主要看模版；
• 这里主要是定义好递归返回值:返回当前树的路径端点和；
• 递归尽可能不用全局变量；

代码

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

    public int preOrder(TreeNode root, int val){
        if(root == null) return -1;

        val = 10 * val + root.val;

        int l = preOrder(root.left, val);
        int r = preOrder(root.right, val);

        if(l == -1 && r == -1) {
            return val;
        } else{
            return (l == -1?0:l) + (r == -1?0:r);
        }

    }
}

复杂度

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

[qixuan-code]

class Solution:
    def sumNumbers(self,root):
        self.res = []
        self.dfs(root,'')
        #sum(int(a) for a in res)
        return sum(int(a) for a in self.res)

    def dfs(self,root,path):
        if root:
            path += str(root.val)
            if not root.left and not root.right:
                self.res.append(path)
            else:
                self.dfs(root.left,path)
                self.dfs(root.right,path)

[MengyuZang]

Problem

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

Solution

1. Add the value of each path together
2. DFS

Code

class Solution {
    int sum = 0;
    public int sumNumbers(TreeNode root) {
        if(root == null) return 0;
        dfs(root, 0);  
        return sum;
    }
    private void dfs(TreeNode node, int parentVal)
    {
        int childVal = parentVal*10 + node.val;
        if(node.left == null && node.right == null){
            sum += childVal;
            return;
        }
        if(node.left != null) dfs(node.left, childVal);
        if(node.right != null) dfs(node.right,childVal);
    }
}

Complexity

Time: O(N) traverse each node

Space: O(H) height of the tree, best: O(lgN), worse: O(N)

[ZJP1483469269]

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

[Frederickfan]

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);

    }
}

[rzhao010]

Thoughts

DFS: each time we visit a new level, the current value should * 10, then add the node.val, if it's the leaf node, return the total value.

Code

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

    private int dfs(TreeNode root, int i) {
        if (root == null) {
            return 0;
        }

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

        return dfs(root.left, tmp) + dfs(root.right, tmp);
    }
}

Complexity

• Time: O(n), every node visited once
• Space: O(n), stack size

[Yutong-Dai]

class Solution(object):
    def isSameTree(self, p, q):
        """
        :type p: TreeNode
        :type q: TreeNode
        :rtype: bool
        """
        # case 1: p is none and q is none
        if p is None and q is None: return True
        # case 2: (p is none and q is not none) or (p is not none and q is none)
        # one trick here:
        # when ( p is None or q is None) is true,
        # it could be  
        #   p is None and q is None (this is excluded by the previous check)
        #   p is not None and q is None
        #   p is None and q is not None
        # For later two cases, we return false
        if p is None or q is None: return False
        # early termination, avoid further recursion
        if p.val != q.val: return False
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

[stackvoid]

思路

树的层序遍历；每次到下一层遍历都要 * 10，中间结果保存比较重要，看题目条件即可。

代码

• 语言支持：Java

Java Code:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int sumNumbers(TreeNode root) {
        if (root == null) return 0;

        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        int ans = 0;
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node.left != null) {
                node.left.val = node.val * 10 + node.left.val;
                queue.offer(node.left);
            }
            if (node.right != null) {
                node.right.val = node.val * 10 + node.right.val;
                queue.offer(node.right);
            }
            if (node.left == null && node.right == null) {
                ans += node.val;
            }
        }
        return ans;
    }
}

复杂度分析

令 n 为数组长度。

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

[Toms-BigData]

【Day 15】129. 求根到叶子节点数字之和

思路

先序遍历的应用，用一个外部变量保存和，每层*10+node.val向下传递，叶子节点加和。

golang代码

func sumNumbers(root *TreeNode) int {
    var ans = 0
    if root==nil{
        return 0
    }
    preorderTraversal(root, 0,&ans)
    return ans
}
func preorderTraversal(node *TreeNode,num int, ans *int) {
    if node.Left == nil && node.Right == nil{
        *ans += num*10+node.Val
    }
    if node.Left!=nil{
        preorderTraversal(node.Left, num*10+node.Val, ans)
    }
    if node.Right!=nil{
        preorderTraversal(node.Right, num*10+node.Val, ans)
    }
}

复杂度

时间：O(n) 空间:O(n)

[hdyhdy]

思路：利用dfs解决。

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

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

时间复杂度 n 空间复杂度 为h，最多的时候为n

[Flower-F]

解题思路

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) {
    if (!root) {
        return 0;
    }
    let res = 0;
    dfs(root, 0);
    return res;

    function dfs(root, sum) {
        if (!root) {
            return;
        }

        sum = sum * 10 + root.val;

        // 到达叶子节点
        if (!root.left && !root.right) {
            res += sum;
        }

        dfs(root.left, sum);
        dfs(root.right, sum);
    }
};

复杂度

时间：O(N)，N为节点个数 空间：O(H)，H为树高

[tongxw]

思路

后序DFS

代码

class Solution {
    public int sumNumbers(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return root.val;
        }

        int total = 0;
        if (root.left != null) {
            root.left.val += root.val * 10;
            total += sumNumbers(root.left);
        }
        if (root.right != null) {
            root.right.val += root.val * 10;
            total += sumNumbers(root.right);
        }
        return total;
    }
}

SC: O(N) TC: O(logN)

[taojin1992]

      1
   /.     \
  2.       3

      1
   /.     \
 2.       3
       /.     \ 
       2.     0

idea: pre-order traversal, leaf (both children null) then update the sum, otherwise, traverse the children and update curSum during recursion

Time: O(n), n = number of nodes
Space: O(height)

/*
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

class Solution {
    public int sumNumbers(TreeNode root) {
        int[] sum = new int[1];
        sumUp(root, 0, sum);
        return sum[0];
    }

    private void sumUp(TreeNode cur, int curSum, int[] sum) {
        if (cur == null) return;
        if (cur.left == null && cur.right == null) {
            curSum = curSum * 10 + cur.val;
            sum[0] += curSum;
            return;
        }
        sumUp(cur.left, curSum * 10 + cur.val, sum);
        sumUp(cur.right, curSum * 10 + cur.val, sum);
    }

}

[a244629128]

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);
};

[CodingProgrammer]

思路

到达一个节点时，计算累加和，并加该累加和继续往下传递。当到达叶子节点时，将该路径上的累加和加到最终的 res 中

代码

class Solution {
    int res;

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

    }

    private void dfs(TreeNode node, int sum) {
        if (node == null)
            return;

        sum = 10 * sum + node.val;

        // 到达叶子节点
        if (node.left == null && node.right == null) {
            res += sum;
        }

        dfs(node.left, sum);
        dfs(node.right, sum);
    }
}

复杂度

• Time: O(N)
• Space: O(H)

[gentleman-goodman]

Day_15_129_求根节点到叶节点数字之和.md

思路

一开始就想用dfs，递归思想，一个问题就是不知道怎么去让root.val的值变成整数，1-2=>12这样子
想的还是for循环之类的，没想到居然可以preSum*10+preSum即可解决，佩服；
另外就是不知道递归的情况，这题是两个子节点都空才算return，之前是分左右子节点的情况
这题不用，都是递归去，最后++

> > ```

代码

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

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

            return dfs(root.left, preSum) + dfs(root.right, preSum);
        }
    }

复杂度分析

[arteecold]

看评论里有老哥还能画出来二叉树图 真猛

class Solution:
    def sumNumbers(self, root: TreeNode) -> 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)

[aladingzl]

思路

看到二叉树第一时间想到 DFS、BFS，想到归想到，就是不知道怎么去处理这个过程，本来想记录层数，来处理个十百千位，好像不太行，看了题解，可以这样

代码

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

复杂度分析

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

[haixiaolu]

思路

想到了用DFS和BFS， 但是不明白如果头节点 -> 左子树 和 头节点-> 右子树相加的和如果进1怎么处理， 还是太菜！！！

代码 / Python

class Solution:
    def sumNumbers(self, root: Optional[TreeNode]) -> int:
        # DFS
        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(h)

[zhiyuanpeng]

class Solution:
    def sumNumbersHelper(self, root, value, values):
        if root:
            value = value*10 + root.val
            if root.left:
                self.sumNumbersHelper(root.left, value, values)
            if root.right:
                self.sumNumbersHelper(root.right, value, values)
            if not root.left and not root.right:
                values.append(value)

    def sumNumbers(self, root: Optional[TreeNode]) -> int:
        values = []
        value = 0
        self.sumNumbersHelper(root, value, values)
        return sum(values)

time O(N), space O(N)

[GaoMinghao]

思路

使用DFS，似乎还有回溯

代码

class Solution {
    List<Integer> numberRecords = new ArrayList<>();

    public void DFS(TreeNode treeNode, int value) {
        value = value * 10 + treeNode.val;
        if(treeNode.left == null && treeNode.right == null) {
            numberRecords.add(value);
            return;
        }
        if(treeNode.left !=null) {
            DFS(treeNode.left, value);
        }
        if(treeNode.right != null) {
            DFS(treeNode.right, value);
        }
    }

    public int sumNumbers(TreeNode root) {
        DFS(root,0);
        int result = 0;
        for(int v:numberRecords) {
            result+=v;
        }
        return result;
    }
}

复杂度

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