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 and inorder consist of unique values.
Each value of inorder also appears in preorder.
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[..])
    }
}

105 - Construct Binary Tree from Preorder and Inorder Traversal

Question

Algorithm

Note

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Note

Code

All Problems

All Solutions