leetcode Binary Tree Depth-First Search

leetcode 129题

Posted by franki on November 16, 2020

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

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

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

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

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

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/sum-root-to-leaf-numbers 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

示例

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sum-root-to-leaf-numbers
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

利用深度优先搜索，把根节点到叶子节点的组成的数相加获取最终的值

代码

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

复杂度分析

  • 时间复杂度: O(n)
  • 空间复杂度: O(1)
CATALOG
    FEATURED TAGS
    前端开发 H5 JavaScript 设计模式 browser jQuery 源码分析 生活 leetcode Array Stack Queue Linked List 剑指offer Binary Search Tree Binary Tree Breadth-First Search Depth-First Search String Set Binary Search Sliding Window Backtracking Dynamic Programming Two Pointers Union Find Sort Bit Operation Recursion Map Graph Search Hash LinkedList 复盘 QuickSort Trie Design MinHeap Traverse Min Heap Node.js BackEnd SQL MySQL Design Patterns Network 计算机网络 Python SVG
    FRIENDS