Lstmxx的空间

889. 根据前序和后序遍历构造二叉树

返回与给定的前序和后序遍历匹配的任何二叉树。

pre 和 post 遍历中的值是不同的正整数。

链接

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function constructFromPrePost(pre: number[], post: number[]): TreeNode | null {
  function travese(preIndex: number, postIndex: number, N: number) {
    if (N === 0) return null
    const root = new TreeNode(pre[preIndex])
    if (N === 1) return root

    let L = 1
    const leftRootIndex = preIndex + 1
    for(; L < N; ++L) {
      if (post[postIndex + L - 1] === pre[leftRootIndex]) break
    }

    root.left = travese(leftRootIndex, postIndex, L)
    root.right = travese(leftRootIndex + L, L + postIndex, N - L - 1)
    return root
  }
  return travese(0, 0, pre.length)
};