Skip to main content

105. Construct Binary Tree from Preorder and Inorder Traversal

分析

dfs一把梭

题解

数组

function buildTree(preorder: number[], inorder: number[]): TreeNode | null {
if (!preorder.length) {
return null
}
const rootVal = preorder[0]
const root = new TreeNode(rootVal)
const index = inorder.findIndex(v => v === rootVal)
root.left = buildTree(preorder.slice(1, 1 + index), inorder.slice(0, index))
root.right = buildTree(preorder.slice(1 + index), inorder.slice(index + 1))
return root
};

用四个下表表示两个数组,前者的心智负担更低

function buildTree(preorder: number[], inorder: number[]): TreeNode | null {
const n = preorder.length

const dfs = (preorderLeft, preorderRight, inorderLeft, inorderRight): TreeNode | null => {
if (preorderLeft > preorderRight) {
return null
}
const root = new TreeNode(preorder[preorderLeft])
if (preorderLeft === preorderRight) {
return root
}
const mid = inorder.findIndex(v => v === preorder[preorderLeft])
const leftTreeLen = mid - inorderLeft
root.left = dfs(preorderLeft + 1, preorderLeft + 1 + leftTreeLen - 1, inorderLeft, mid - 1)
root.right = dfs(preorderLeft + 1 + leftTreeLen, preorderRight, mid + 1, inorderRight)
return root
}

return dfs(0, n - 1, 0, n - 1)
};