Voyz's Studio.

LeetCode算法笔记--从前序与中序遍历序列构造二叉树

算法题 热题HOT100 二叉树
字数统计: 284阅读时长: 1 min
2020/12/28 Share

LeetCode算法笔记-Day53

105. Construct Binary Tree from Preorder and Inorder Traversal

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:You may assume that duplicates do not exist in the tree.

example: 

1
2
3
4
5
6
7
8
9
10
preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]

Return the following binary tree:

    3
   / \
  9  20
    /  \
   15   7

Analyse:

  • 变量 pre 保存当前要构造的树的 root
  • 变量 in 保存 inorder 数组中可以成为 root 的数字们的开头那个
  • 对于当前要构造的树，有一个停止点 stop ，inorder 数组中第 in 项到第 stop 项是要构造的树的节点值们
  • 每次递归调用，都会确定出一个停止点，它告诉了子调用在哪里停止，把自己的根节点值作为左子树调用的停止点，自己的（父调用给下来的）停止点作为右子树的停止点  

Answer：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */

var buildTree = function(preorder, inorder) {
    pre = i = 0
    build = function(stop) {
        if (inorder[i] != stop) {
            var root = new TreeNode(preorder[pre++])
            root.left = build(root.val)
            i++
            root.right = build(stop)
            return root
        }
        return null
    }
    return build()
};
CATALOG
  1. 1. LeetCode算法笔记-Day53
    1. 1.1. 105. Construct Binary Tree from Preorder and Inorder Traversal
    2. 1.2. Analyse:
      1. 1.2.1. Answer：
Total : 137
2021
2020
2019
2018
技术贴 JavaScript Flutter 算法题 热题HOT100 哈希表 滑动窗口 回溯算法 链表 二分法 矩阵 动态规划 贪心算法 指针 快速排序 迭代 二叉树 数组 快慢指针 排序 背包问题 单调栈 栈 DFS 岛屿问题 React Native React 旅行记 效率工具 python 小程序 英语 生活 足球 算法 性能优化 ES6 TypeScript koa