Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/105.html
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.
Example 1:
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] Output: [3,9,20,null,null,15,7]
Example 2:
Input: preorder = [-1], inorder = [-1] Output: [-1]
Constraints:
1 <= preorder.length <= 3000
inorder.length == preorder.length
-3000 <= preorder[i], inorder[i] <= 3000
preorder
andinorder
consist of unique values.- Each value of
inorder
also appears inpreorder
. preorder
is guaranteed to be the preorder traversal of the tree.inorder
is guaranteed to be the inorder traversal of the tree.
Algorithm
Since the first in the order of preorder must be the root, the root node of the original binary tree can be known. A very critical condition is given in the title that there are no identical elements in the tree.
With this condition, it can be traversed in the middle order. Locate the position of the root node, and split the in-order traversal into the left and right parts according to the position of the root node, and call the original function on it recursively.
Note
The pitfall
is that I traverse the inorder and find the position of root
- But
pre.length/2
is wrong, the midpoint is not necessarily directly divided by 2, because the binary tree may not be left-right balanced - So find root from preorder, and then find root in inorder. In inorder, the ones before root are all children on the left
Code
-
import java.util.Arrays; public class Construct_Binary_Tree_from_Preorder_and_Inorder_Traversal { /** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public TreeNode buildTree(int[] preorder, int[] inorder) { return buildTree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1); } TreeNode buildTree(int[] preorder, int pLeft, int pRight, int[] inorder, int iLeft, int iRight) { if (pLeft > pRight || iLeft > iRight) return null; int i = 0; for (i = iLeft; i <= iRight; ++i) { if (preorder[pLeft] == inorder[i]) break; } TreeNode cur = new TreeNode(preorder[pLeft]); cur.left = buildTree(preorder, pLeft + 1, pLeft + (i - iLeft), inorder, iLeft, i - 1); cur.right = buildTree(preorder, pLeft + (i - iLeft) + 1, pRight, inorder, i + 1, iRight); return cur; } } } ############ /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { private Map<Integer, Integer> indexes = new HashMap<>(); public TreeNode buildTree(int[] preorder, int[] inorder) { for (int i = 0; i < inorder.length; ++i) { indexes.put(inorder[i], i); } return dfs(preorder, inorder, 0, 0, preorder.length); } private TreeNode dfs(int[] preorder, int[] inorder, int i, int j, int n) { if (n <= 0) { return null; } int v = preorder[i]; int k = indexes.get(v); TreeNode root = new TreeNode(v); root.left = dfs(preorder, inorder, i + 1, j, k - j); root.right = dfs(preorder, inorder, i + 1 + k - j, k + 1, n - k + j - 1); return root; } }
-
# 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 = right # best class Solution: def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]: if not preorder: # or, not inorder return None v = preorder[0] i = inorder.index(v) root = TreeNode(v) root.left = self.buildTree(preorder[1: i+1], inorder[:i]) root.right = self.buildTree(preorder[i+1:], inorder[i+1:]) return root # inorder.index(preorder_val) class Solution: def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]: def dfs(pleft, pright, ileft, iright): if pleft > pright or ileft > iright: return None k = inorder.index(preorder[pleft]) root = TreeNode(preorder[pleft]) root.left = dfs(pleft + 1, pleft + (k - ileft), ileft, k - 1) root.right = dfs(pleft + 1 + (k - ileft), pright, k + 1, iright) return root n = len(preorder) return dfs(0, n - 1, 0, n - 1) # build dict for val => index class Solution: def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]: def dfs(pleft, pright, ileft, iright): if pleft > pright or ileft > iright: return None v = preorder[pleft] k = d[v] root = TreeNode(v) root.left = dfs(pleft + 1, pleft + (k - ileft), ileft, k - 1) root.right = dfs(pleft + 1 + (k - ileft), pright, k + 1, iright) return root d = {v: i for i, v in enumerate(inorder)} n = len(preorder) return dfs(0, n - 1, 0, n - 1) ############ ''' search for index, also use .index(val) >>> a = [1,2,3,4,5] >>> a.index(3) 2 ''' class Solution(object): def buildTree(self, preorder, inorder): """ :type preorder: List[int] :type inorder: List[int] :rtype: TreeNode """ self.preindex = 0 ind = {v: i for i, v in enumerate(inorder)} head = self.dc(0, len(preorder) - 1, preorder, inorder, ind) return head def dc(self, start, end, preorder, inorder, ind): if start <= end: mid = ind[preorder[self.preindex]] self.preindex += 1 root = TreeNode(inorder[mid]) root.left = self.dc(start, mid - 1, preorder, inorder, ind) root.right = self.dc(mid + 1, end, preorder, inorder, ind) return root
-
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: unordered_map<int, int> indexes; TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { for (int i = 0; i < inorder.size(); ++i) indexes[inorder[i]] = i; return dfs(preorder, inorder, 0, 0, inorder.size()); } TreeNode* dfs(vector<int>& preorder, vector<int>& inorder, int i, int j, int n) { if (n <= 0) return nullptr; int v = preorder[i]; int k = indexes[v]; TreeNode* root = new TreeNode(v); root->left = dfs(preorder, inorder, i + 1, j, k - j); root->right = dfs(preorder, inorder, i + 1 + k - j, k + 1, n - k + j - 1); return root; } };
-
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func buildTree(preorder []int, inorder []int) *TreeNode { indexes := make(map[int]int) for i, v := range inorder { indexes[v] = i } var dfs func(i, j, n int) *TreeNode dfs = func(i, j, n int) *TreeNode { if n <= 0 { return nil } v := preorder[i] k := indexes[v] root := &TreeNode{Val: v} root.Left = dfs(i+1, j, k-j) root.Right = dfs(i+1+k-j, k+1, n-k+j-1) return root } return dfs(0, 0, len(inorder)) }
-
/** * 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 buildTree(preorder: number[], inorder: number[]): TreeNode | null { const n = preorder.length; if (n === 0) { return null; } const val = preorder[0]; const index = inorder.indexOf(val); return new TreeNode( val, buildTree(preorder.slice(1, index + 1), inorder.slice(0, index)), buildTree(preorder.slice(index + 1), inorder.slice(index + 1)), ); }
-
/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {number[]} preorder * @param {number[]} inorder * @return {TreeNode} */ var buildTree = function (preorder, inorder) { function dfs(i, j, n) { if (n <= 0) { return null; } const v = preorder[i]; const k = d[v]; const root = new TreeNode(v); root.left = dfs(i + 1, j, k - j); root.right = dfs(i + 1 + k - j, k + 1, n - k + j - 1); return root; } const d = new Map(); for (const [i, v] of inorder.entries()) { d[v] = i; } return dfs(0, 0, inorder.length); };
-
// Definition for a binary tree node. // #[derive(Debug, PartialEq, Eq)] // pub struct TreeNode { // pub val: i32, // pub left: Option<Rc<RefCell<TreeNode>>>, // pub right: Option<Rc<RefCell<TreeNode>>>, // } // // impl TreeNode { // #[inline] // pub fn new(val: i32) -> Self { // TreeNode { // val, // left: None, // right: None // } // } // } use std::rc::Rc; use std::cell::RefCell; impl Solution { fn to_tree(preorder: &[i32], inorder: &[i32]) -> Option<Rc<RefCell<TreeNode>>> { if preorder.is_empty() { return None; } let val = preorder[0]; let index = inorder.iter().position(|&v| v == val).unwrap(); Some(Rc::new(RefCell::new(TreeNode { val, left: Self::to_tree(&preorder[1..index + 1], &inorder[..index]), right: Self::to_tree(&preorder[index + 1..], &inorder[index + 1..]), }))) } pub fn build_tree(preorder: Vec<i32>, inorder: Vec<i32>) -> Option<Rc<RefCell<TreeNode>>> { Self::to_tree(&preorder[..], &inorder[..]) } }