Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.
preorder is guaranteed to be the preorder traversal of the tree.
inorder is guaranteed to be the inorder traversal of the tree.
Solutions
Solution 1: Hash Table + Recursion
The first node $preorder[0]$ in the pre-order sequence is the root node. We find the position $k$ of the root node in the in-order sequence, which can divide the in-order sequence into the left subtree $inorder[0..k]$ and the right subtree $inorder[k+1..]$.
Through the intervals of the left and right subtrees, we can calculate the number of nodes in the left and right subtrees, assumed to be $a$ and $b$. Then in the pre-order nodes, the $a$ nodes after the root node are the left subtree, and the $b$ nodes after that are the right subtree.
Therefore, we design a function $dfs(i, j, n)$, where $i$ and $j$ represent the starting positions of the pre-order sequence and the in-order sequence, respectively, and $n$ represents the number of nodes. The return value of the function is the binary tree constructed with $preorder[i..i+n-1]$ as the pre-order sequence and $inorder[j..j+n-1]$ as the in-order sequence.
The execution process of the function $dfs(i, j, n)$ is as follows:
If $n \leq 0$, it means there are no nodes, return a null node.
Take out the first node $v = preorder[i]$ of the pre-order sequence as the root node, and then use the hash table $d$ to find the position $k$ of the root node in the in-order sequence. Then the number of nodes in the left subtree is $k - j$, and the number of nodes in the right subtree is $n - k + j - 1$.
Recursively construct the left subtree $l = dfs(i + 1, j, k - j)$ and the right subtree $r = dfs(i + 1 + k - j, k + 1, n - k + j - 1)$.
Finally, return the binary tree with $v$ as the root node and $l$ and $r$ as the left and right subtrees, respectively.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the number of nodes in the binary tree.
1 2 3 4 5 6 7 8 910111213141516171819
# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclassSolution:defbuildTree(self,preorder:List[int],inorder:List[int])->Optional[TreeNode]:defdfs(i:int,j:int,n:int)->Optional[TreeNode]:ifn<=0:returnNonev=preorder[i]k=d[v]l=dfs(i+1,j,k-j)r=dfs(i+1+k-j,k+1,n-k+j-1)returnTreeNode(v,l,r)d={v:ifori,vinenumerate(inorder)}returndfs(0,0,len(preorder))
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */funcbuildTree(preorder[]int,inorder[]int)*TreeNode{d:=map[int]int{}fori,x:=rangeinorder{d[x]=i}vardfsfunc(i,j,nint)*TreeNodedfs=func(i,j,nint)*TreeNode{ifn<=0{returnnil}v:=preorder[i]k:=d[v]l:=dfs(i+1,j,k-j)r:=dfs(i+1+k-j,k+1,n-1-(k-j))return&TreeNode{v,l,r}}returndfs(0,0,len(preorder))}
If the node values given in the problem have duplicates, then we only need to record all the positions where each node value appears, and then recursively construct the tree.