1008. 前序遍历构造二叉搜索树

发表于 | 分类于
栈的思路始终没有想明白，后面再看吧

用时 ： 没做出来

没做出来的主要原因是一直想着怎么用栈来做，写到后面看栈的答案看着看着发现递归最简单

递归

思路很简单，首先写出来怎么插入子节点

  1. 如果比父节点小，且父节点左为空，直接做左节点
  2. 如果比父节点大，且父节点右为空，直接做右节点
  3. 比父节点小，则父节点赋值为父节点的左节点，回到 1
  4. 比父节点大，则父节点赋值为父节点的右节点，回到1

遍历整个数组，一个个插入即可得到结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
var bstFromPreorder = function(preorder) {
    var add = function (node,val) {
        if (val < node.val && !node.left) {
            node.left = new TreeNode(val)
        }
        if (val > node.val && !node.right) {
            node.right = new TreeNode(val)
        }
        if (val < node.val) {
            add(node.left,val)
        }
        if (val > node.val) {
            add(node.right,val)
        }
    }
    var root = new TreeNode(preorder.shift())
    for(let i = 0 ; i < preorder.length ; i ++) {
        add(root,preorder[i])
    }
    return root
};