Binary Tree in Action (Construction)

labuladongOriginalAbout 9437 words

Note

Now all the plugins has supported English. I'm still improving the website...

This article will resolve

LeetCode	Difficulty
105. Construct Binary Tree from Preorder and Inorder Traversal	🟠
106. Construct Binary Tree from Inorder and Postorder Traversal	🟠
654. Maximum Binary Tree	🟠
889. Construct Binary Tree from Preorder and Postorder Traversal	🟠

Prerequisites

Before reading this article, you need to learn:

This article follows up on Binary Tree Methodology (Outline). Let's first recap the binary tree problem-solving outline summarized in the previous article:

Note

There are two main approaches to solving binary tree problems:

1. Can you get the answer by traversing the binary tree once? If so, use a traverse function combined with external variables. This is called the "traversal" approach.

2. Can you define a recursive function that derives the answer to the original problem from the answers to subproblems (subtrees)? If so, write out the definition of this recursive function and make full use of its return value. This is called the "decompose problem" approach.

Regardless of which approach you use, you need to consider:

If you isolate a single binary tree node, what does it need to do? When does it need to do it (pre-order, in-order, post-order)? Other nodes are handled by the recursive function, which will perform the same operation on all nodes.

The first article Binary Tree Methodology (Thinking) discussed the two approaches: "traversal" and "decompose problem". This article focuses on construction problems in binary trees.

Binary tree construction problems generally use the "decompose problem" approach: constructing the whole tree = root node + constructing the left subtree + constructing the right subtree.

Let's dive into the problem.

Constructing the Maximum Binary Tree

Let's start with an easy one, Problem 654 on LeetCode, "Maximum Binary Tree". The problem is as follows:

654. Maximum Binary Tree | LeetCode |

You are given an integer array nums with no duplicates. A maximum binary tree can be built recursively from nums using the following algorithm:

Create a root node whose value is the maximum value in nums.
Recursively build the left subtree on the subarray prefix to the left of the maximum value.
Recursively build the right subtree on the subarray suffix to the right of the maximum value.

Return the maximum binary tree built from nums.

Example 1:

Input: nums = [3,2,1,6,0,5]
Output: [6,3,5,null,2,0,null,null,1]
Explanation: The recursive calls are as follow:
- The largest value in [3,2,1,6,0,5] is 6. Left prefix is [3,2,1] and right suffix is [0,5].
    - The largest value in [3,2,1] is 3. Left prefix is [] and right suffix is [2,1].
        - Empty array, so no child.
        - The largest value in [2,1] is 2. Left prefix is [] and right suffix is [1].
            - Empty array, so no child.
            - Only one element, so child is a node with value 1.
    - The largest value in [0,5] is 5. Left prefix is [0] and right suffix is [].
        - Only one element, so child is a node with value 0.
        - Empty array, so no child.

Example 2:

Input: nums = [3,2,1]
Output: [3,null,2,null,1]

Constraints:

1 <= nums.length <= 1000
0 <= nums[i] <= 1000
All integers in nums are unique.

java 🟢

// function signature as follows
TreeNode constructMaximumBinaryTree(int[] nums);

cpp 🤖

// The function signature is as follows
TreeNode* constructMaximumBinaryTree(vector<int>& nums);

python 🤖

# The function signature is as follows
def constructMaximumBinaryTree(nums: List[int]) -> TreeNode:

go 🤖

// The function signature is as follows
func constructMaximumBinaryTree(nums []int) *TreeNode

javascript 🤖

// function signature as follows
var constructMaximumBinaryTree = function(nums) {};

Each node in a binary tree can be considered the root of a subtree. For the root node, the first thing to do is to construct itself, and then find a way to construct its left and right subtrees.

Therefore, we need to traverse the array to find the maximum value maxVal, then create the root node root with this value. Next, we recursively construct the left subtree from the elements to the left of maxVal and the right subtree from the elements to the right of maxVal.

According to the example given in the problem, the input array is [3,2,1,6,0,5]. For the root node of the entire tree, we are essentially doing this:

java 🟢

TreeNode constructMaximumBinaryTree([3,2,1,6,0,5]) {
    // find the maximum value in the array
    TreeNode root = new TreeNode(6);
    // recursively construct the left and right subtrees
    root.left = constructMaximumBinaryTree([3,2,1]);
    root.right = constructMaximumBinaryTree([0,5]);
    return root;
}

// the maximum value in the current nums is the root node, and then
// recursively call the left and right arrays to construct the left and right
// in more detail, the pseudocode is as follows
TreeNode constructMaximumBinaryTree(int[] nums) {
    if (nums is empty) return null;
    // find the maximum value in the array
    int maxVal = Integer.MIN_VALUE;
    int index = 0;
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] > maxVal) {
            maxVal = nums[i];
            index = i;
        }
    }

    TreeNode root = new TreeNode(maxVal);
    // recursively construct the left and right subtrees
    root.left = constructMaximumBinaryTree(nums[0..index-1]);
    root.right = constructMaximumBinaryTree(nums[index+1..nums.length-1]);
    return root;
}

cpp 🤖

TreeNode* constructMaximumBinaryTree([3,2,1,6,0,5]) {
    // find the maximum value in the array
    TreeNode* root = new TreeNode(6);
    // recursively construct the left and right subtrees
    root->left = constructMaximumBinaryTree({3,2,1});
    root->right = constructMaximumBinaryTree({0,5});
    return root;
}

// the current maximum value in nums is the root node, and then
// recursively construct the left and right subtrees based on the
// more specifically, the pseudocode is as follows
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
    if (nums.empty()) return nullptr;

    // find the maximum value in the array
    int maxVal = INT_MIN;
    int index = 0;
    for (int i = 0; i < nums.size(); i++) {
        if (nums[i] > maxVal) {
            maxVal = nums[i];
            index = i;
        }
    }

    TreeNode* root = new TreeNode(maxVal);
    // recursively construct the left and right subtrees
    root->left = constructMaximumBinaryTree(nums[0..index-1]);
    root->right = constructMaximumBinaryTree(nums[index+1..nums.size()-1]);
}

python 🤖

def constructMaximumBinaryTree([3,2,1,6,0,5]) -> TreeNode:
    # find the maximum value in the array
    root = TreeNode(6)
    # recursively construct the left and right subtrees
    root.left = constructMaximumBinaryTree([3,2,1])
    root.right = constructMaximumBinaryTree([0,5])
    return root

# the current maximum value in nums is the root node, then recursively
# construct the left and right subtrees based on the indices of the
# in more detail, the pseudocode is as follows
def constructMaximumBinaryTree(nums: List[int]) -> TreeNode:
    if not nums: 
        return None

    # find the maximum value in the array
    maxVal = max(nums)
    index = nums.index(maxVal)

    root = TreeNode(maxVal)
    # recursively construct the left and right subtrees
    root.left = constructMaximumBinaryTree(nums[:index])
    root.right = constructMaximumBinaryTree(nums[index+1:])
    return root

go 🤖

func constructMaximumBinaryTree([3,2,1,6,0,5]) *TreeNode {
    // find the maximum value in the array
    root := &TreeNode{Val: 6}
    // recursively construct left and right subtrees
    root.Left = constructMaximumBinaryTree([]int{3,2,1})
    root.Right = constructMaximumBinaryTree([]int{0,5})
    return root
}

// the current maximum value in nums is the root node, and then
// recursively construct left and right subtrees based on the index
// in more detail, the pseudocode is as follows
func constructMaximumBinaryTree(nums []int) *TreeNode {
    if len(nums) == 0 {
        return nil
    }
    // find the maximum value in the array
    maxVal := math.MinInt32
    index := 0
    for i := 0; i < len(nums); i++ {
        if nums[i] > maxVal {
            maxVal = nums[i]
            index = i
        }
    }

    root := &TreeNode{Val: maxVal}
    // recursively construct left and right subtrees
    root.Left = constructMaximumBinaryTree(nums[:index])
    root.Right = constructMaximumBinaryTree(nums[index+1:])
    return root
}

javascript 🤖

var constructMaximumBinaryTree = function([3,2,1,6,0,5]) {
    // find the maximum value in the array
    var root = new TreeNode(6);
    // recursively construct the left and right subtrees
    root.left = constructMaximumBinaryTree([3,2,1]);
    root.right = constructMaximumBinaryTree([0,5]);
    return root;
}

// the maximum value in the current nums is the root node, then
// recursively construct the left and right subtrees based on the
// in more detail, it is as follows in pseudocode
var constructMaximumBinaryTree = function(nums) {
    if (nums.length === 0) return null;

    // find the maximum value in the array
    var maxVal = Math.min(...nums);
    var index = nums.indexOf(maxVal);

    var root = new TreeNode(maxVal);
    // recursively construct the left and right subtrees
    root.left = constructMaximumBinaryTree(nums.slice(0, index));
    root.right = constructMaximumBinaryTree(nums.slice(index + 1, nums.length));
    
    return root;
}

The maximum value in the current nums is the root node. Then, recursively call the left and right arrays based on the index to construct the left and right subtrees.

With this idea clear, we can write an auxiliary function build to control the indices of nums:

java 🟢

class Solution {

    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return build(nums, 0, nums.length - 1);
    }

    // Definition: Construct a tree from nums[lo..hi]
    // that meets the conditions, return the root node
    TreeNode build(int[] nums, int lo, int hi) {
        // base case
        if (lo > hi) {
            return null;
        }

        // Find the maximum value in the array and its corresponding index
        int index = -1, maxVal = Integer.MIN_VALUE;
        for (int i = lo; i <= hi; i++) {
            if (maxVal < nums[i]) {
                index = i;
                maxVal = nums[i];
            }
        }

        // First construct the root node
        TreeNode root = new TreeNode(maxVal);
        // Recursively construct the left and right subtrees
        root.left = build(nums, lo, index - 1);
        root.right = build(nums, index + 1, hi);
        
        return root;
    }
}

cpp 🤖

class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        return build(nums, 0, nums.size()-1);
    }

private:
    // Definition: Construct a tree from nums[lo..hi]
    // that meets the conditions and return the root
    TreeNode* build(vector<int>& nums, int lo, int hi) {
        // base case
        if (lo > hi) {
            return nullptr;
        }

        // Find the maximum value in the array and its corresponding index
        int index = -1, maxVal = INT_MIN;
        for (int i = lo; i <= hi; i++) {
            if (maxVal < nums[i]) {
                index = i;
                maxVal = nums[i];
            }
        }

        // First, construct the root node
        TreeNode* root = new TreeNode(maxVal);
        // Recursively construct the left and right subtrees
        root->left = build(nums, lo, index - 1);
        root->right = build(nums, index + 1, hi);
        
        return root;
    }
};

python 🤖

class Solution:
    def constructMaximumBinaryTree(self, nums: List[int]) -> TreeNode:
        return self.build(nums, 0, len(nums) - 1)

    # Definition: Construct the tree that meets the
    # requirements from nums[lo..hi] and return the root
    def build(self, nums: List[int], lo: int, hi: int) -> TreeNode:
        # base case
        if lo > hi:
            return None

        # Find the maximum value in the array and its corresponding index
        index = -1
        maxVal = float('-inf')
        for i in range(lo, hi + 1):
            if maxVal < nums[i]:
                index = i
                maxVal = nums[i]

        # First, construct the root node
        root = TreeNode(maxVal)
        # Recursively construct the left and right subtrees
        root.left = self.build(nums, lo, index - 1)
        root.right = self.build(nums, index + 1, hi)
        
        return root

go 🤖

func constructMaximumBinaryTree(nums []int) *TreeNode {
    return build(nums, 0, len(nums) - 1)
}

// Definition: construct a tree with nums[lo..hi]
// that meets the conditions, and return the root node
func build(nums []int, lo, hi int) *TreeNode {
    // base case
    if lo > hi {
        return nil
    }

    // find the maximum value in the array and its corresponding index
    index := -1
    maxVal := -1 << 31
    for i := lo; i <= hi; i++ {
        if maxVal < nums[i] {
            index = i
            maxVal = nums[i]
        }
    }

    // first construct the root node
    root := &TreeNode{Val: maxVal}
    // recursively construct the left and right subtrees
    root.Left = build(nums, lo, index - 1)
    root.Right = build(nums, index + 1, hi)
    
    return root
}

javascript 🤖

var constructMaximumBinaryTree = function(nums) {
    return build(nums, 0, nums.length - 1);
}

// Definition: construct a tree from nums[lo..hi]
// that meets the conditions, and return the root node
function build(nums, lo, hi) {
    // base case
    if (lo > hi) {
        return null;
    }

    // find the maximum value in the array and its corresponding index
    let index = -1, maxVal = Number.MIN_SAFE_INTEGER;
    for (let i = lo; i <= hi; i++) {
        if (maxVal < nums[i]) {
            index = i;
            maxVal = nums[i];
        }
    }

    // first, construct the root node
    let root = new TreeNode(maxVal);
    // recursively construct the left and right subtrees
    root.left = build(nums, lo, index - 1);
    root.right = build(nums, index + 1, hi);
    
    return root;
}

So, we have completed this problem. It was quite simple, wasn't it? Now, let's look at two more challenging ones.

Constructing a Binary Tree from Preorder and Inorder Traversal

LeetCode Problem 105, "Construct Binary Tree from Preorder and Inorder Traversal," is a classic question that is frequently asked in interviews and written tests:

105. Construct Binary Tree from Preorder and Inorder Traversal | LeetCode |

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.

java 🟢

// The function signature is as follows
TreeNode buildTree(int[] preorder, int[] inorder);

cpp 🤖

// The function signature is as follows
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder);

python 🤖

# the function signature is as follows
def buildTree(preorder: List[int], inorder: List[int]):

go 🤖

// The function signature is as follows
func buildTree(preorder []int, inorder []int) *TreeNode

javascript 🤖

// The function signature is as follows
var buildTree = function(preorder, inorder) {};

Let's get straight to the point and think about the approach. First, consider what the root node should do.

Similar to the previous problem, we need to determine the value of the root node, create the root node, and then recursively construct the left and right subtrees.

Let's review the characteristics of the preorder and inorder traversal results.

java 🟢

void traverse(TreeNode root) {
    // preorder traversal
    preorder.add(root.val);
    traverse(root.left);
    traverse(root.right);
}

void traverse(TreeNode root) {
    traverse(root.left);
    // inorder traversal
    inorder.add(root.val);
    traverse(root.right);
}

cpp 🤖

void traverse(TreeNode* root) {
    if(root == NULL)
        return;
    // pre-order traversal
    preorder.push_back(root->val);
    traverse(root->left);
    traverse(root->right);
}

void traverse(TreeNode* root) {
    if(root == NULL)
        return;
    traverse(root->left);
    // in-order traversal
    inorder.push_back(root->val);
    traverse(root->right);
}

python 🤖

def traverse(root):
    if not root:
        return
    # pre-order traversal
    preorder.append(root.val)
    traverse(root.left)
    traverse(root.right)

def traverse(root):
    if not root:
        return
    traverse(root.left)
    # in-order traversal
    inorder.append(root.val)
    traverse(root.right)

go 🤖

func traverse(root *TreeNode) {
    if root == nil {
        return
    }
    // preorder traversal
    preorder = append(preorder, root.Val)
    traverse(root.Left)
    traverse(root.Right)
}

func traverse(root *TreeNode) {
    if root == nil {
        return
    }
    traverse(root.Left)
    // inorder traversal
    inorder = append(inorder, root.Val)
    traverse(root.Right)
}

javascript 🤖

var traverse = function(root) {
    if (root === null) {
        return;
    }
    // preorder traversal
    preorder.push(root.val);
    traverse(root.left);
    traverse(root.right);
}

var traverse = function(root) {
    if (root === null) {
        return;
    }
    traverse(root.left);
    // inorder traversal
    inorder.push(root.val);
    traverse(root.right);
}

In the previous article The Frameworks of Binary Trees, it was discussed how the different traversal orders lead to certain characteristics in the distribution of elements in the preorder and inorder arrays:

Finding the root node is quite simple; the first value preorder[0] in the preorder traversal is the root node's value.

The key question is how to use the root node's value to divide the preorder and inorder arrays into two halves to construct the left and right subtrees of the root node.

In other words, what should be filled in the ? part of the following code:

java 🟢

TreeNode buildTree(int[] preorder, int[] inorder) {
    // According to the function definition, construct
    // the binary tree using preorder and inorder
    return build(preorder, 0, preorder.length - 1,
                inorder, 0, inorder.length - 1);
}

// Definition of the build function:
// If the preorder traversal array is preorder[preStart..preEnd],
// and the inorder traversal array is inorder[inStart..inEnd],
// construct the binary tree and return its root node
TreeNode build(int[] preorder, int preStart, int preEnd, 
            int[] inorder, int inStart, int inEnd) {
    // The value of the root node corresponds to the first element of the preorder array
    int rootVal = preorder[preStart];
    // The index of rootVal in the inorder array
    int index = 0;
    for (int i = inStart; i <= inEnd; i++) {
        if (inorder[i] == rootVal) {
            index = i;
            break;
        }
    }

    TreeNode root = new TreeNode(rootVal);
    // Recursively construct the left and right subtrees
    root.left = build(preorder, ?, ?,
                    inorder, ?, ?);

    root.right = build(preorder, ?, ?,
                    inorder, ?, ?);
    return root;
}

cpp 🤖

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    // According to the function definition,
    // construct the binary tree using preorder and
    return build(preorder, 0, preorder.size() - 1,
                inorder, 0, inorder.size() - 1);
}

// Definition of the build function:
// If the preorder traversal array is preorder[preStart..preEnd],
// and the inorder traversal array is inorder[inStart..inEnd],
// build the binary tree and return the root node of the tree
TreeNode* build(vector<int>& preorder, int preStart, int preEnd,
                vector<int>& inorder, int inStart, int inEnd) {
    if (preStart > preEnd) {
        return NULL;
    }
    // The value of the root node is the first element of the preorder traversal array
    int rootVal = preorder[preStart];
    int index;
    for (int i = inStart; i<= inEnd; i++) {
        // The index of rootVal in the inorder traversal array
        if (inorder[i] == rootVal) {
            index = i;
            break;
        }
    }
    TreeNode* root = new TreeNode(rootVal);
    int leftSize = index - inStart;
    // Recursively construct the left and right subtrees
    root->left = build(preorder, ?, ?,
                    inorder, ?, ?);

    root->right = build(preorder, ?, ?,
                    inorder, ?, ?);
    return root;
}

python 🤖

def buildTree(preorder, inorder):
    # According to the function definition, use
    # preorder and inorder to construct the binary
    return build(preorder, 0, len(preorder) - 1,
                inorder, 0, len(inorder) - 1)

# Definition of build function:
# If the preorder traversal array is preorder[preStart..preEnd],
# and the inorder traversal array is inorder[inStart..inEnd],
# construct the binary tree and return its root node
def build(preorder, preStart, preEnd, 
            inorder, inStart, inEnd):
    # The value of the root node is the first element in the preorder traversal array
    rootVal = preorder[preStart]
    # The index of rootVal in the inorder traversal array
    index = 0
    for i in range(inStart, inEnd + 1):
        if inorder[i] == rootVal:
            index = i
            break

    root = TreeNode(rootVal)
    # Recursively construct the left and right subtrees
    root.left = build(preorder, ?, ?,
                    inorder, ?, ?)

    root.right = build(preorder, ?, ?,
                    inorder, ?, ?)
    return root

go 🤖

func buildTree(preorder []int, inorder []int) *TreeNode {
    // According to the function definition,
    // construct the binary tree using preorder and
    return build(preorder, 0, len(preorder)-1, inorder, 0, len(inorder)-1)
}

// Definition of the build function:
// If the preorder traversal array is preorder[preStart..preEnd],
// and the inorder traversal array is inorder[inStart..inEnd],
// construct the binary tree and return its root node
func build(preorder []int, preStart int, preEnd int, 
           inorder []int, inStart int, inEnd int) *TreeNode {
    if preStart > preEnd {
        return nil
    }
    // The value corresponding to the root node is the first element of the preorder array
    rootVal := preorder[preStart]
    // The index of rootVal in the inorder array
    index := 0
    for i := inStart; i <= inEnd; i++ {
        if inorder[i] == rootVal {
            index = i
            break
        }
    }
    root := &TreeNode{Val: rootVal}
    sizeLeftSubtree := index - inStart
    // Recursively construct the left and right subtrees
    root.Left = build(preorder, ?, ?,
                    inorder, ?, ?)
    root.Right = build(preorder, ?, ?,
                    inorder, ?, ?)
    return root
}

javascript 🤖

var buildTree = function(preorder, inorder) {
    // According to the function definition,
    // construct the binary tree using preorder and
    return build(preorder, 0, preorder.length - 1,
                inorder, 0, inorder.length - 1);
}

// Definition of the build function:
// If the preorder traversal array is preorder[preStart..preEnd],
// and the inorder traversal array is inorder[inStart..inEnd],
// construct the binary tree and return the root node of the binary tree
var build = function(preorder, preStart, preEnd, 
                    inorder, inStart, inEnd) {
    // The value corresponding to the root node is
    // the first element of the preorder traversal
    var rootVal = preorder[preStart];

    // The index of rootVal in the inorder traversal array
    var index = 0;
    for (var i = inStart; i <= inEnd; i++) {
        if (inorder[i] === rootVal) {
            index = i;
            break;
        }
    }

    var root = new TreeNode(rootVal);

    // Recursively construct the left and right subtrees
    root.left = build(preorder, ?, ?,
                    inorder, ?, ?);

    root.right = build(preorder, ?, ?,
                    inorder, ?, ?);

    return root;
}

In the code, the variables rootVal and index refer to the situation illustrated in the image below:

Additionally, some readers have pointed out that using a for loop to determine index is not very efficient and can be further optimized.

Since the problem states that the values of the binary tree nodes are unique, a HashMap can be used to store the mapping of elements to their indices. This allows you to directly find the index corresponding to rootVal using the HashMap:

java 🟢

// store the value-to-index mapping in inorder
HashMap<Integer, Integer> valToIndex = new HashMap<>();

public TreeNode buildTree(int[] preorder, int[] inorder) {
    for (int i = 0; i < inorder.length; i++) {
        valToIndex.put(inorder[i], i);
    }
    return build(preorder, 0, preorder.length - 1,
                 inorder, 0, inorder.length - 1);
}

TreeNode build(int[] preorder, int preStart, int preEnd, 
               int[] inorder, int inStart, int inEnd) {
    int rootVal = preorder[preStart];
    // avoid using a for loop to find rootVal
    int index = valToIndex.get(rootVal);
    // ...
}

cpp 🤖

// store the mapping of values to indices in inorder
unordered_map<int, int> valToIndex;

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    for (int i = 0; i < inorder.size(); i++) {
        valToIndex[inorder[i]] = i;
    }
    return build(preorder, 0, preorder.size() - 1,
                 inorder, 0, inorder.size() - 1);
}

TreeNode* build(vector<int>& preorder, int preStart, int preEnd, 
                vector<int>& inorder, int inStart, int inEnd) {
    int rootVal = preorder[preStart];
    // avoid using a for loop to find rootVal
    int index = valToIndex[rootVal];
    // ...
}

python 🤖

# store the mapping from values to indices in inorder
val_to_index = {}

def build_tree(preorder, inorder):

    for i in range(len(inorder)):
        val_to_index[inorder[i]] = i

    return build(preorder, 0, len(preorder) - 1,
                 inorder, 0, len(inorder) - 1)

def build(preorder, pre_start, pre_end, 
          inorder, in_start, in_end):
  
    root_val = preorder[pre_start]
    # avoid using for loop to find rootVal
    index = val_to_index[root_val]
    # ...

go 🤖

// store the mapping from values to indices in inorder
valToIndex := make(map[int]int)

func buildTree(preorder []int, inorder []int) *TreeNode {
    for i := 0; i < len(inorder); i++ {
        valToIndex[inorder[i]] = i
    }
    return build(preorder, 0, len(preorder) - 1,
                 inorder, 0, len(inorder) - 1)
}

func build(preorder []int, preStart int, preEnd int,
           inorder []int, inStart int, inEnd int) *TreeNode {
           
    rootVal := preorder[preStart]
    // avoid using a for loop to find rootVal
    index := valToIndex[rootVal]
    // ...
}

javascript 🤖

// store the mapping from values to indices in inorder
var valToIndex = {};

var buildTree = function(preorder, inorder) {
    for (var i = 0; i < inorder.length; i++) {
        valToIndex[inorder[i]] = i;
    }
    return build(preorder, 0, preorder.length - 1,
                 inorder, 0, inorder.length - 1);
};

var build = function(preorder, preStart, preEnd, 
               inorder, inStart, inEnd) {
    var rootVal = preorder[preStart];
    // avoid using a for loop to find rootVal
    var index = valToIndex[rootVal];
    // ...
};

Now let's look at the picture and fill in the blanks. What should be filled in the question marks below:

java 🟢

root.left = build(preorder, ?, ?,
                  inorder, ?, ?);

root.right = build(preorder, ?, ?,
                   inorder, ?, ?);

cpp 🤖

root->left = build(preorder, ?, ?,
                   inorder, ?, ?);

root->right = build(preorder, ?, ?,
                   inorder, ?, ?);

python 🤖

root.left = build(preorder, ?, ?,
                  inorder, ?, ?)

root.right = build(preorder, ?, ?,
                   inorder, ?, ?)

go 🤖

root.Left = build(preorder, ?, ?,
                  inorder, ?, ?)

root.Right = build(preorder, ?, ?,
                   inorder, ?, ?)

javascript 🤖

root.left = build(preorder, ?, ?,
                  inorder, ?, ?);

root.right = build(preorder, ?, ?,
                   inorder, ?, ?);

The starting and ending indices for the inorder arrays corresponding to the left and right subtrees are relatively easy to determine:

java 🟢

root.left = build(preorder, ?, ?,
                  inorder, inStart, index - 1);

root.right = build(preorder, ?, ?,
                   inorder, index + 1, inEnd);

cpp 🤖

root->left = build(preorder, ?, ?,
                   inorder, inStart, index - 1);

root->right = build(preorder, ?, ?,
                   inorder, index + 1, inEnd);

python 🤖

root.left = build(preorder, ?, ?, inorder, inStart, index - 1)

root.right = build(preorder, ?, ?, inorder, index + 1, inEnd)

go 🤖

root.Left = build(preorder, ?, ?, 
                  inorder, inStart, index - 1)

root.Right = build(preorder, ?, ?, 
                   inorder, index + 1, inEnd)

javascript 🤖

root.left = build(preorder, ?, ?, 
                inorder, inStart, index - 1);

root.right = build(preorder, ?, ?, 
                    inorder, index + 1, inEnd);

How about the preorder array? How do we determine the starting and ending indices for the left and right subarrays?

This can be deduced from the number of nodes in the left subtree. Let's assume the number of nodes in the left subtree is leftSize. The index situation in the preorder array is as follows:

By looking at this diagram, you can write out the corresponding indices for the preorder array:

java 🟢

int leftSize = index - inStart;

root.left = build(preorder, preStart + 1, preStart + leftSize,
                  inorder, inStart, index - 1);

root.right = build(preorder, preStart + leftSize + 1, preEnd,
                   inorder, index + 1, inEnd);

cpp 🤖

int leftSize = index - inStart;

root->left = build(preorder, preStart + 1, preStart + leftSize,
                   inorder, inStart, index - 1);

root->right = build(preorder, preStart + leftSize + 1, preEnd,
                    inorder, index + 1, inEnd);

python 🤖

leftSize = index - inStart

root.left = build(preorder, preStart + 1, preStart + leftSize,
                  inorder, inStart, index - 1)

root.right = build(preorder, preStart + leftSize + 1, preEnd,
                   inorder, index + 1, inEnd)

go 🤖

leftSize := index - inStart

root.Left = build(preorder, preStart + 1, preStart + leftSize,
                  inorder, inStart, index - 1)

root.Right = build(preorder, preStart + leftSize + 1, preEnd,
                   inorder, index + 1, inEnd)

javascript 🤖

var leftSize = index - inStart;

root.left = build(preorder, preStart + 1, preStart + leftSize,
                  inorder, inStart, index - 1);

root.right = build(preorder, preStart + leftSize + 1, preEnd,
                   inorder, index + 1, inEnd);

At this point, the entire algorithm approach is complete. We just need to handle the base case to write the solution code:

java 🟢

class Solution {
    // Store the mapping of values to indices in inorder
    HashMap<Integer, Integer> valToIndex = new HashMap<>();

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for (int i = 0; i < inorder.length; i++) {
            valToIndex.put(inorder[i], i);
        }
        return build(preorder, 0, preorder.length - 1,
                    inorder, 0, inorder.length - 1);
    }

    // Definition of the build function:
    // If the preorder traversal array is preorder[preStart..preEnd],
    // and the inorder traversal array is inorder[inStart..inEnd],
    // construct the binary tree and return its root node
    TreeNode build(int[] preorder, int preStart, int preEnd, 
               int[] inorder, int inStart, int inEnd) {

        if (preStart > preEnd) {
            return null;
        }

        // The value of the root node corresponds to the first element in the preorder array
        int rootVal = preorder[preStart];
        // The index of rootVal in the inorder array
        int index = valToIndex.get(rootVal);

        int leftSize = index - inStart;

        // First, construct the current root node
        TreeNode root = new TreeNode(rootVal);
        // Recursively construct the left and right subtrees
        root.left = build(preorder, preStart + 1, preStart + leftSize,
                        inorder, inStart, index - 1);

        root.right = build(preorder, preStart + leftSize + 1, preEnd,
                        inorder, index + 1, inEnd);
        return root;
    }
}

cpp 🤖

class Solution {
public:
    // store the mapping from value to index in inorder
    unordered_map<int, int> valToIndex;

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        for (int i = 0; i < inorder.size(); i++) {
            valToIndex[inorder[i]] = i;
        }
        return build(preorder, 0, preorder.size() - 1,
                    inorder, 0, inorder.size() - 1);
    }

    // definition of build function:
    // if the preorder array is preorder[preStart..preEnd],
    // and the inorder array is inorder[inStart..inEnd],
    // construct the binary tree and return its root node
    TreeNode* build(vector<int>& preorder, int preStart, int preEnd, 
                    vector<int>& inorder, int inStart, int inEnd) {

        if (preStart > preEnd) {
            return NULL;
        }

        // the value of the root node is the first element of the preorder array
        int rootVal = preorder[preStart];
        // the index of rootVal in the inorder array
        int index = valToIndex[rootVal];

        int leftSize = index - inStart;

        // first construct the current root node
        TreeNode* root = new TreeNode(rootVal);
        // recursively construct the left and right subtrees
        root->left = build(preorder, preStart + 1, preStart + leftSize,
                        inorder, inStart, index - 1);

        root->right = build(preorder, preStart + leftSize + 1, preEnd,
                        inorder, index + 1, inEnd);
        return root;
    }
};

python 🤖

class Solution:
    # store the mapping from values in inorder to their indices
    valToIndex = dict()

    def buildTree(self, preorder, inorder):
        for i in range(len(inorder)):
            self.valToIndex[inorder[i]] = i
        return self.build(preorder, 0, len(preorder) - 1,
                          inorder, 0, len(inorder) - 1)

    # definition of the build function:
    # if the preorder traversal array is preorder[preStart..preEnd],
    # and the inorder traversal array is inorder[inStart..inEnd],
    # construct the binary tree and return its root node
    def build(self, preorder, preStart, preEnd,
               inorder, inStart, inEnd):
        if preStart > preEnd:
            return None

        # the root node's value is the first element in the preorder array
        rootVal = preorder[preStart]
        # the index of rootVal in the inorder array
        index = self.valToIndex[rootVal]

        leftSize = index - inStart

        # first construct the current root node
        root = TreeNode(rootVal) 

        # recursively construct the left and right subtrees
        root.left = self.build(preorder, preStart + 1, preStart + leftSize,
                               inorder, inStart, index - 1)

        root.right = self.build(preorder, preStart + leftSize + 1, preEnd,
                                inorder, index + 1, inEnd)

        return root

go 🤖

func buildTree(preorder []int, inorder []int) *TreeNode {
    valToIndex := make(map[int]int)
    for i := 0; i < len(inorder); i++ {
        valToIndex[inorder[i]] = i
    }

    var build func([]int, int, int, []int, int, int) *TreeNode
    build = func(preorder []int, preStart, preEnd int, inorder []int, inStart, inEnd int) *TreeNode {
        if preStart > preEnd {
            return nil
        }

        // the value corresponding to the root node is the first element of the preorder array
        rootVal := preorder[preStart]
        // the index of rootVal in the inorder array
        index := valToIndex[rootVal]
        leftSize := index - inStart

        // first construct the current root node
        root := &TreeNode{Val: rootVal}
        // recursively construct the left and right subtrees
        root.Left = build(preorder, preStart+1, preStart+leftSize, inorder, inStart, index-1)
        root.Right = build(preorder, preStart+leftSize+1, preEnd, inorder, index+1, inEnd)
        return root
    }

    return build(preorder, 0, len(preorder)-1, inorder, 0, len(inorder)-1)
}

javascript 🤖

var buildTree = function(preorder, inorder) {
    // store the mapping from value to index in inorder
    var valToIndex = new Map();

    for (let i = 0; i < inorder.length; i++) {
        valToIndex.set(inorder[i], i);
    }
    return build(preorder, 0, preorder.length - 1,
                inorder, 0, inorder.length - 1);

    // definition of build function:
    // if the preorder array is preorder[preStart..preEnd],
    // and the inorder array is inorder[inStart..inEnd],
    // construct the binary tree and return its root node
    function build(preorder, preStart, preEnd, 
               inorder, inStart, inEnd) {

        if (preStart > preEnd) {
            return null;
        }

        // the value of the root node is the first element of the preorder array
        var rootVal = preorder[preStart];
        // the index of rootVal in the inorder array
        var index = valToIndex.get(rootVal);

        var leftSize = index - inStart;

        // first construct the current root node
        var root = new TreeNode(rootVal);
        // recursively build the left and right subtrees
        root.left = build(preorder, preStart + 1, preStart + leftSize,
                        inorder, inStart, index - 1);

        root.right = build(preorder, preStart + leftSize + 1, preEnd,
                        inorder, index + 1, inEnd);
        return root;
    }
};

Our main function only needs to call the buildTree function. Although there are many parameters and the solution seems complicated, it may appear more daunting compared to the previous problem. In reality, these parameters merely control the start and end positions of the arrays, which can be easily managed with a diagram.

Constructing a Binary Tree from Postorder and Inorder Traversal Results

Similar to the previous problem, this time we will use the result arrays of postorder and inorder traversal to reconstruct the binary tree. This is LeetCode Problem 106: "Construct Binary Tree from Inorder and Postorder Traversal."

106. Construct Binary Tree from Inorder and Postorder Traversal | LeetCode |

Given two integer arrays inorder and postorder where inorder is the inorder traversal of a binary tree and postorder is the postorder traversal of the same tree, construct and return the binary tree.

Example 1:

Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
Output: [3,9,20,null,null,15,7]

Example 2:

Input: inorder = [-1], postorder = [-1]
Output: [-1]

Constraints:

1 <= inorder.length <= 3000
postorder.length == inorder.length
-3000 <= inorder[i], postorder[i] <= 3000
inorder and postorder consist of unique values.
Each value of postorder also appears in inorder.
inorder is guaranteed to be the inorder traversal of the tree.
postorder is guaranteed to be the postorder traversal of the tree.

java 🟢

// The function signature is as follows
TreeNode buildTree(int[] inorder, int[] postorder);

cpp 🤖

// The function signature is as follows
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder);

python 🤖

# The function signature is as follows
def buildTree(inorder: List[int], postorder: List[int]) -> TreeNode:

go 🤖

// The function signature is as follows
func buildTree(inorder []int, postorder []int) *TreeNode

javascript 🤖

// The function signature is as follows
var buildTree = function(inorder, postorder) {}

类似的，看下后序和中序遍历的特点：

java 🟢

void traverse(TreeNode root) {
    traverse(root.left);
    traverse(root.right);
    // postorder traversal
    postorder.add(root.val);
}

void traverse(TreeNode root) {
    traverse(root.left);
    // inorder traversal
    inorder.add(root.val);
    traverse(root.right);
}

cpp 🤖

void traverse(TreeNode* root) {
    if (root == NULL) return;
  
    traverse(root->left);
    traverse(root->right);
    
    // postorder traversal
    postorder.push_back(root->val);
}

void traverse(TreeNode* root) {
    if (root == NULL) return;
    
    traverse(root->left);
    
    // inorder traversal
    inorder.push_back(root->val);
    
    traverse(root->right);
}

python 🤖

def traverse(root):
    if root:
        traverse(root.left)
        traverse(root.right)
        # postorder traversal
        postorder.append(root.val)

def traverse(root):
    if root:
        traverse(root.left)
        # inorder traversal
        inorder.append(root.val)
        traverse(root.right)

go 🤖

func traverse(root *TreeNode) {
    if root == nil {
        return
    }
    traverse(root.Left)
    traverse(root.Right)
    // postorder traversal
    postorder = append(postorder, root.Val)
}

func traverse(root *TreeNode) {
    if root == nil {
        return
    }
    traverse(root.Left)
    // inorder traversal
    inorder = append(inorder, root.Val)
    traverse(root.Right)
}

javascript 🤖

var traverse = function(root) {
    if (root==null) { 
      return; 
    }
    traverse(root.left);
    traverse(root.right);
    // post-order traversal
    postorder.push(root.val);
}

var traverse = function(root) {
    if (root==null) { 
      return; 
    }
    traverse(root.left);
    // in-order traversal
    inorder.push(root.val);
    traverse(root.right);
}

The difference in traversal order results in the following characteristics in the distribution of elements in the postorder and inorder arrays:

The key difference between this problem and the previous one is that in postorder traversal, unlike preorder, the root node corresponds to the last element of the postorder array.

The overall algorithm framework is very similar to the previous problem. We will still write a helper function called build:

java 🟢

class Solution {
    // Store the mapping from values to indices in the inorder array
    HashMap<Integer, Integer> valToIndex = new HashMap<>();

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        for (int i = 0; i < inorder.length; i++) {
            valToIndex.put(inorder[i], i);
        }
        return build(inorder, 0, inorder.length - 1,
                    postorder, 0, postorder.length - 1);
    }

    // Definition of the build function:
    // The postorder traversal array is postorder[postStart..postEnd],
    // The inorder traversal array is inorder[inStart..inEnd],
    // Construct the binary tree and return its root node
    TreeNode build(int[] inorder, int inStart, int inEnd,
                int[] postorder, int postStart, int postEnd) {
        // The value of the root node is the last element of the postorder traversal array
        int rootVal = postorder[postEnd];
        // The index of rootVal in the inorder traversal array
        int index = valToIndex.get(rootVal);

        TreeNode root = new TreeNode(rootVal);
        // Recursively construct the left and right subtrees
        root.left = build(inorder, ?, ?,
                        postorder, ?, ?);

        root.right = build(inorder, ?, ?,
                        postorder, ?, ?);
        return root;
    }
}

cpp 🤖

class Solution {
public:
    // store the mapping from value to index in inorder
    unordered_map<int, int> valToIndex;

    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        for (int i = 0; i < inorder.size(); i++) {
            valToIndex[inorder[i]] = i;
        }
        return build(inorder, 0, inorder.size() - 1,
                     postorder, 0, postorder.size() - 1);
    }

// definition of build function:
// postorder traversal array is postorder[postStart..postEnd],
// inorder traversal array is inorder[inStart..inEnd],
// construct the binary tree, return the root node of the tree
TreeNode* build(vector<int>& inorder, int inStart, int inEnd,
                vector<int>& postorder, int postStart, int postEnd) {
        // the value of the root node is the last element in the postorder array
        int rootVal = postorder[postEnd];
        // index of rootVal in the inorder array
        int index = valToIndex[rootVal];

        TreeNode* root = new TreeNode(rootVal);
        // recursively construct the left and right subtrees
        root->left = build(inorder, ?, ?,
                           postorder, ?, ?);

        root->right = build(inorder, ?, ?,
                            postorder, ?, ?);
        return root;
    }
};

python 🤖

class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
        # store the mapping from value to index in inorder
        valToIndex = {val: idx for idx, val in enumerate(inorder)}

        # definition of build function:
        # postorder traversal array is postorder[postStart..postEnd],
        # inorder traversal array is inorder[inStart..inEnd],
        # construct the binary tree, return the root node of this tree
        def build(in_left, in_right, post_left, post_right):
            if in_left > in_right: return
            
            # the value of the root node is the last element of the postorder traversal array
            root_val = postorder[post_right]
            # the index of rootVal in the inorder traversal array
            index = valToIndex[root_val]

            root = TreeNode(root_val)
            # recursively construct the left and right subtrees
            size_left_subtree = index - in_left
            root.left = build(inorder, ?, ?,
                               postorder, ?, ?)
            root.right = build(inorder, ?, ?,
                                postorder, ?, ?)
            
            return root

        return build(0, len(inorder) - 1, 0, len(postorder) - 1)

go 🤖

func buildTree(inorder []int, postorder []int) *TreeNode {
    // store the mapping from value to index in inorder
    valToIndex := make(map[int]int)
    for i, v := range inorder {
        valToIndex[v] = i
    }

    // definition of build function:
    // postorder array is postorder[postStart..postEnd],
    // inorder array is inorder[inStart..inEnd],
    // construct the binary tree, return the root node of the tree
    var build func(inStart int, inEnd int, postStart int, postEnd int) *TreeNode
    build = func(inStart int, inEnd int, postStart int, postEnd int) *TreeNode {
        if inStart > inEnd {
            return nil
        }

        // the value of root node is the last element of postorder array
        rootVal := postorder[postEnd]
        // index of rootVal in inorder array
        index := valToIndex[rootVal]

        root := &TreeNode{Val: rootVal}
        // recursively construct the left and right subtrees
        root.Left = build(inorder, ?, ?,
                           postorder, ?, ?);
        root.Right = build(inorder, ?, ?,
                            postorder, ?, ?);

        return root
    }

    return build(0, len(inorder)-1, 0, len(postorder)-1)
}

javascript 🤖

var buildTree = function(inorder, postorder) {
    // store the mapping of values to indices in inorder
    var valToIndex = {};
    for (let i = 0; i < inorder.length; i++) {
        valToIndex[inorder[i]] = i;
    }

    // definition of the build function:
    // the postorder traversal array is postorder[postStart..postEnd],
    // the inorder traversal array is inorder[inStart..inEnd],
    // construct the binary tree and return the root node of this tree
    function build(inStart, inEnd, postStart, postEnd) {
        // if no elements to construct subtrees
        if (inStart > inEnd) {
            return null; 
        }

        // the value of the root node is the last element in the postorder traversal array
        let rootVal = postorder[postEnd];
        // the index of rootVal in the inorder traversal array
        let index = valToIndex[rootVal];
        
        var root = new TreeNode(rootVal);
        // recursively construct the left and right subtrees
        root.left = build(inorder, ?, ?,
                           postorder, ?, ?);
        root.right = build(inorder, ?, ?,
                           postorder, ?, ?);
        
        return root;
    }
    return build(0, inorder.length - 1, 0, postorder.length - 1);
};

The current states of postorder and inorder are as follows:

We can correctly fill in the index at the question mark location according to the diagram above:

java 🟢

int leftSize = index - inStart;

root.left = build(inorder, inStart, index - 1,
                  postorder, postStart, postStart + leftSize - 1);

root.right = build(inorder, index + 1, inEnd,
                   postorder, postStart + leftSize, postEnd - 1);

cpp 🤖

int leftSize = index - inStart;

root->left = build(inorder, inStart, index - 1,
                  postorder, postStart, postStart + leftSize - 1);

root->right = build(inorder, index + 1, inEnd,
                   postorder, postStart + leftSize, postEnd - 1);

python 🤖

leftSize = index - inStart

root.left = build(inorder, inStart, index - 1,
                  postorder, postStart, postStart + leftSize - 1)

root.right = build(inorder, index + 1, inEnd,
                   postorder, postStart + leftSize, postEnd - 1)

go 🤖

leftSize := index - inStart

root.Left = build(inorder, inStart, index - 1,
                  postorder, postStart, postStart + leftSize - 1)

root.Right = build(inorder, index + 1, inEnd,
                   postorder, postStart + leftSize, postEnd - 1)

javascript 🤖

var leftSize = index - inStart;

root.left = build(inorder, inStart, index - 1,
                  postorder, postStart, postStart + leftSize - 1);

root.right = build(inorder, index + 1, inEnd,
                   postorder, postStart + leftSize, postEnd - 1);

综上，可以写出完整的解法代码：

java 🟢

class Solution {
    // store the mapping from value to index in inorder
    HashMap<Integer, Integer> valToIndex = new HashMap<>();

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        for (int i = 0; i < inorder.length; i++) {
            valToIndex.put(inorder[i], i);
        }
        return build(inorder, 0, inorder.length - 1,
                    postorder, 0, postorder.length - 1);
    }

    // the definition of the build function:
    // the postorder array is postorder[postStart..postEnd],
    // the inorder array is inorder[inStart..inEnd],
    // construct the binary tree and return its root node
    TreeNode build(int[] inorder, int inStart, int inEnd,
                int[] postorder, int postStart, int postEnd) {

        if (inStart > inEnd) {
            return null;
        }
        // the value of the root node is the last element of the postorder array
        int rootVal = postorder[postEnd];
        // the index of rootVal in the inorder array
        int index = valToIndex.get(rootVal);
        // the number of nodes in the left subtree
        int leftSize = index - inStart;
        TreeNode root = new TreeNode(rootVal);
        // recursively construct the left and right subtrees
        root.left = build(inorder, inStart, index - 1,
                            postorder, postStart, postStart + leftSize - 1);
        
        root.right = build(inorder, index + 1, inEnd,
                            postorder, postStart + leftSize, postEnd - 1);
        return root;
    }
}

cpp 🤖

class Solution {
public:
    // store the mapping from value to index in inorder
    unordered_map<int, int> valToIndex;
    
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        for (int i = 0; i < inorder.size(); i++) {
            valToIndex[inorder[i]] = i;
        }
        return build(inorder, 0, inorder.size() - 1,
                    postorder, 0, postorder.size() - 1);
    }
    
    // definition of the build function:
    // the postorder traversal array is postorder[postStart..postEnd],
    // the inorder traversal array is inorder[inStart..inEnd],
    // construct the binary tree and return the root node
    TreeNode* build(vector<int>& inorder, int inStart, int inEnd,
                vector<int>& postorder, int postStart, int postEnd) {

        if (inStart > inEnd) {
            return nullptr;
        }
        // the value of the root node is the last element in the postorder traversal array
        int rootVal = postorder[postEnd];
        // the index of rootVal in the inorder traversal array
        int index = valToIndex[rootVal];
        // the number of nodes in the left subtree
        int leftSize = index - inStart;
        TreeNode* root = new TreeNode(rootVal);
        // recursively construct the left and right subtrees
        root->left = build(inorder, inStart, index - 1,
                            postorder, postStart, postStart + leftSize - 1);
        
        root->right = build(inorder, index + 1, inEnd,
                            postorder, postStart + leftSize, postEnd - 1);
        return root;
    }
};

python 🤖

class Solution:
    # store the mapping of values to indices in inorder
    valToIndex = {}

    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
        for i in range(len(inorder)):
            self.valToIndex[inorder[i]] = i
        return self.build(inorder, 0, len(inorder) - 1,
                    postorder, 0, len(postorder) - 1)

    # definition of the build function:
    # postorder traversal array is postorder[postStart..postEnd],
    # inorder traversal array is inorder[inStart..inEnd],
    # construct the binary tree and return its root node
    def build(self, inorder, inStart, inEnd, postorder, postStart, postEnd):

        if inStart > inEnd:
            return None
        # the value of the root node is the last element in the postorder traversal array
        rootVal = postorder[postEnd]
        # index of rootVal in the inorder traversal array
        index = self.valToIndex[rootVal]
        # number of nodes in the left subtree
        leftSize = index - inStart
        root = TreeNode(rootVal) 
        # recursively construct the left and right subtrees
        root.left = self.build(inorder, inStart, index - 1, postorder, postStart, postStart + leftSize - 1)
        root.right = self.build(inorder, index + 1, inEnd, postorder, postStart + leftSize, postEnd - 1)
        
        return root

go 🤖

func buildTree(inorder []int, postorder []int) *TreeNode {
	valToIndex := make(map[int]int)
	for i := 0; i < len(inorder); i++ {
		valToIndex[inorder[i]] = i
	}
    
	return build(inorder, postorder, valToIndex, 0, len(inorder)-1, 0, len(postorder)-1)
}

// Definition of the build function:
// The postorder traversal array is postorder[postStart..postEnd],
// The inorder traversal array is inorder[inStart..inEnd],
// Construct the binary tree and return its root node.
func build(inorder []int, postorder []int, valToIndex map[int]int, inStart int, inEnd int, postStart int, postEnd int) *TreeNode {
	if inStart > inEnd {
		return nil
	}
	// The value of the root node is the last element in the postorder traversal array.
	rootVal := postorder[postEnd]
	// The index of rootVal in the inorder traversal array.
	index := valToIndex[rootVal]
	// The number of nodes in the left subtree.
	leftSize := index - inStart
	root := &TreeNode{Val: rootVal}
	// Recursively construct the left and right subtrees.
	root.Left = build(inorder, postorder, valToIndex, inStart, index-1, postStart, postStart+leftSize-1)

	root.Right = build(inorder, postorder, valToIndex, index+1, inEnd, postStart+leftSize, postEnd-1)

	return root
}

javascript 🤖

var buildTree = function(inorder, postorder) {
    // store the mapping from value to index in inorder
    let valToIndex = {};

    for (let i = 0; i < inorder.length; i++) {
        valToIndex[inorder[i]] = i;
    }

    // definition of build function:
    // postorder traversal array is postorder[postStart..postEnd],
    // inorder traversal array is inorder[inStart..inEnd],
    // construct the binary tree and return its root node
    function build(inorder, inStart, inEnd, postorder, postStart, postEnd) {
        if (inStart > inEnd) {
            return null;
        }
        // the value of the root node is the last element in the postorder array
        let rootVal = postorder[postEnd];
        // index of rootVal in inorder array
        let index = valToIndex[rootVal];
        // number of nodes in the left subtree
        let leftSize = index - inStart;

        let root = new TreeNode(rootVal);
        // recursively construct the left and right subtrees
        root.left = build(inorder, inStart, index - 1,
                            postorder, postStart, postStart + leftSize - 1);
        
        root.right = build(inorder, index + 1, inEnd,
                            postorder, postStart + leftSize, postEnd - 1);
        return root;
    }

    return build(inorder, 0, inorder.length - 1,
                    postorder, 0, postorder.length - 1);
};

With the foundation from the previous question, this problem is quickly resolved. Essentially, rootVal becomes the last element, and you only need to adjust the parameters of the recursive function. As long as you understand the properties of binary trees, it's not difficult to write.

Constructing a Binary Tree from Postorder and Preorder Traversal Results

This is LeetCode Problem 889 "Construct Binary Tree from Preorder and Postorder Traversal." You are given the preorder and postorder traversal results of a binary tree and asked to reconstruct the structure of the binary tree.

The function signature is as follows:

java 🟢

TreeNode constructFromPrePost(int[] preorder, int[] postorder);

cpp 🤖

TreeNode* constructFromPrePost(vector<int>& preOrder, vector<int>& postOrder);

python 🤖

from typing import List

def constructFromPrePost(preorder: List[int], postorder: List[int]) -> TreeNode:

go 🤖

func constructFromPrePost(preorder []int, postorder []int) *TreeNode

javascript 🤖

var constructFromPrePost = function(preorder, postorder) {}

This problem has a fundamental difference from the previous two:

With preorder and inorder or postorder and inorder traversal results, you can determine a unique original binary tree. However, using preorder and postorder results alone cannot determine a unique original binary tree.

The problem statement also mentions that if there are multiple possible reconstruction results, you can return any one of them.

Why is this the case? As we have discussed, the strategy for constructing a binary tree is quite straightforward: first, identify the root node, then recursively construct the left and right subtrees.

In the previous two problems, you could identify the root node using the preorder or postorder traversal results, and then determine the left and right subtrees using the inorder traversal results (the problem states that there are no nodes with the same val in the tree).

In this problem, you can determine the root node, but you cannot precisely identify which nodes belong to the left or right subtrees.

For example, consider this input:

preorder = [1,2,3], postorder = [3,2,1]

Both of the following trees satisfy the conditions, but clearly, their structures are different:

That said, reconstructing a binary tree using postorder and preorder results involves a logic similar to the previous problems, where you control the indices of the left and right subtrees to construct them:

1. First, determine the root node's value using the first element of the preorder result or the last element of the postorder result.

2. Then, take the second element of the preorder result as the root node's value of the left subtree.

3. Locate the value of the left subtree's root node in the postorder result to determine the index boundaries for the left subtree, which in turn allows you to determine the index boundaries for the right subtree, and recursively construct the left and right subtrees.

See the code for details.

java 🟢

class Solution {
    // Store the mapping from value to index in postorder
    HashMap<Integer, Integer> valToIndex = new HashMap<>();

    public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
        for (int i = 0; i < postorder.length; i++) {
            valToIndex.put(postorder[i], i);
        }
        return build(preorder, 0, preorder.length - 1,
                    postorder, 0, postorder.length - 1);
    }

    // Definition: build the binary tree from
    // preorder[preStart..preEnd] and
    // and return the root node.
    TreeNode build(int[] preorder, int preStart, int preEnd,
                   int[] postorder, int postStart, int postEnd) {
        if (preStart > preEnd) {
            return null;
        }
        if (preStart == preEnd) {
            return new TreeNode(preorder[preStart]);
        }

        // The value of the root node is the first element in the preorder array
        int rootVal = preorder[preStart];
        // The value of root.left is the second element in the preorder array
        // The key to constructing a binary tree from preorder and postorder is to
        // determine the element range of left and right subtrees through the root of the
        // in preorder and postorder
        int leftRootVal = preorder[preStart + 1];
        // The index of leftRootVal in the postorder array
        int index = valToIndex.get(leftRootVal);
        // The number of elements in the left subtree
        int leftSize = index - postStart + 1;

        // First, construct the current root node
        TreeNode root = new TreeNode(rootVal);
        // Recursively construct the left and right subtrees
        // Derive the index boundaries of the left and right subtrees
        // based on the root index and the number of elements in the left
        root.left = build(preorder, preStart + 1, preStart + leftSize,
                postorder, postStart, index);
        root.right = build(preorder, preStart + leftSize + 1, preEnd,
                postorder, index + 1, postEnd - 1);

        return root;
    }
}

cpp 🤖

class Solution {
    // store the mapping of values to indices in postorder
    unordered_map<int, int> valToIndex;

public:
    TreeNode* constructFromPrePost(vector<int>& preorder, vector<int>& postorder) {
        for (int i = 0; i < postorder.size(); i++) {
            valToIndex[postorder[i]] = i;
        }
        return build(preorder, 0, preorder.size() - 1,
                    postorder, 0, postorder.size() - 1);
    }

    // Definition: construct a binary tree based on
    // preorder[preStart..preEnd] and
    // and return the root node.
    TreeNode* build(vector<int>& preorder, int preStart, int preEnd,
                   vector<int>& postorder, int postStart, int postEnd) {
        if (preStart > preEnd) {
            return nullptr;
        }
        if (preStart == preEnd) {
            return new TreeNode(preorder[preStart]);
        }

        // the value of the root node corresponds to the first element of the preorder array
        int rootVal = preorder[preStart];
        // root.left's value is the second element of the preorder array
        // the key to constructing a binary tree using preorder and
        // postorder is to determine the element range of the left and
        // in preorder and postorder based on the root node of the left subtree
        int leftRootVal = preorder[preStart + 1];
        // the index of leftRootVal in the postorder array
        int index = valToIndex[leftRootVal];
        // the number of elements in the left subtree
        int leftSize = index - postStart + 1;

        // first construct the current root node
        TreeNode* root = new TreeNode(rootVal);
        // recursively construct the left and right subtrees
        // deduce the index boundaries of the left and right subtrees based
        // on the root node index and the number of elements of the left
        root->left = build(preorder, preStart + 1, preStart + leftSize,
                postorder, postStart, index);
        root->right = build(preorder, preStart + leftSize + 1, preEnd,
                postorder, index + 1, postEnd - 1);

        return root;
    }
};

python 🤖

class Solution:
    # store the mapping from value to index in postorder
    valToIndex = dict()

    def constructFromPrePost(self, preorder, postorder):
        for i in range(len(postorder)):
            self.valToIndex[postorder[i]] = i
        return self.build(preorder, 0, len(preorder) - 1,
                          postorder, 0, len(postorder) - 1)

    # definition: construct the binary tree based on
    # preorder[preStart..preEnd] and
    # build the binary tree and return the root node.
    def build(self, preorder, preStart, preEnd,
              postorder, postStart, postEnd):
        if preStart > preEnd:
            return None
        if preStart == preEnd:
            return TreeNode(preorder[preStart])

        # the value of the root node is the first element in the preorder array
        rootVal = preorder[preStart]
        # the value of root.left is the second element in preorder
        # the key to constructing the binary tree using preorder and postorder is to
        # determine the element range of the left and right subtrees using the root node of
        # determine the element range of the left and right subtrees in preorder and postorder
        leftRootVal = preorder[preStart + 1]
        # the index of leftRootVal in the postorder array
        index = self.valToIndex[leftRootVal]
        # the number of elements in the left subtree
        leftSize = index - postStart + 1
     
        # first construct the current root node
        root = TreeNode(rootVal) 
        # recursively construct the left and right subtrees
        # derive the index boundaries of the left and right subtrees
        # based on the root node index and the number of elements in the
        root.left = self.build(preorder, preStart + 1, preStart + leftSize,
                               postorder, postStart, index)
        root.right = self.build(preorder, preStart + leftSize + 1, preEnd,
                                postorder, index + 1, postEnd - 1)

        return root

go 🤖

func constructFromPrePost(preorder []int, postorder []int) *TreeNode{
    // store the mapping from values to indices in postorder
    valToIndex := make(map[int]int)

    for i := 0; i < len(postorder); i++ {
        valToIndex[postorder[i]] = i
    }

    // definition: build a binary tree based on
    // preorder[preStart..preEnd] and postorder[postStart..postEnd],
    var build func(preorder []int, preStart, preEnd int, postorder []int, postStart, postEnd int) *TreeNode
	build = func(preorder []int, preStart, preEnd int, postorder []int, postStart, postEnd int) *TreeNode {    
    	if preStart > preEnd {
        	return nil
    	}
    	if preStart == preEnd {
        	return &TreeNode{
				Val:   preorder[preStart],
				Left:  nil,
				Right: nil,
			}
    	}

    	// the value of the root node corresponds to the first element in the preorder array
    	rootVal := preorder[preStart]
    	// the value of root.left is the second element in the preorder array
    	// the key to constructing a binary tree from preorder and postorder traversals is
// determining the element ranges of the left and right subtrees via the root node of the left
    	// determine the element ranges of the left and right subtrees in preorder and postorder
    	leftRootVal := preorder[preStart + 1]
    	// the index of leftRootVal in the postorder array
    	index := valToIndex[leftRootVal]
    	// the number of elements in the left subtree
    	leftSize := index - postStart + 1

    	// first construct the current root node
    	root := &TreeNode{
			Val:   rootVal,
			Left:  nil,
			Right: nil,
		}

    	// recursively construct the left and right subtrees
    	// deduce the index boundaries of the left and right subtrees based on
// the root node index and the number of elements in the left subtree
    	root.Left = build(preorder, preStart + 1, preStart + leftSize, postorder, postStart, index)
    	root.Right = build(preorder, preStart + leftSize + 1, preEnd, postorder, index + 1, postEnd - 1)

    	return root
    }

    return build(preorder, 0, len(preorder) - 1, postorder, 0, len(postorder) - 1)
}

javascript 🤖

var constructFromPrePost = function(preorder, postorder) {
    // store the mapping from values to indices in postorder

    const valToIndex = {};
    for (let i = 0; i < postorder.length; i++) {
        valToIndex[postorder[i]] = i;
    }

// definition: build the binary tree based on
// preorder[preStart..preEnd] and postorder[postStart..postEnd] and
var build = function(preorder, preStart, preEnd, postorder, postStart, postEnd) {
    if (preStart > preEnd) {
        return null;
    }
    if (preStart === preEnd) {
        return new TreeNode(preorder[preStart]);
    }

    // the value of the root node corresponds to the first element of the preorder array
    let rootVal = preorder[preStart];
    // the value of root.left is the second element of the preorder array
    // the key to constructing the binary tree through preorder and
    // postorder traversal lies in the root node of the left subtree
    // determine the element ranges of the left and right subtrees in preorder and postorder
    let leftRootVal = preorder[preStart + 1];
    // the index of leftRootVal in the postorder array
    let index = valToIndex[leftRootVal];
    // the number of elements in the left subtree
    let leftSize = index - postStart + 1;

    // first, construct the current root node
    let root = new TreeNode(rootVal);
    // recursively construct the left and right subtrees
    // deduce the index boundaries of the left and right subtrees based
    // on the root node index and the number of elements of the left
    root.left = build(preorder, preStart + 1, preStart + leftSize,
            postorder, postStart, index);
    root.right = build(preorder, preStart + leftSize + 1, preEnd,
            postorder, index + 1, postEnd - 1);

    return root;
};

    return build(preorder, 0, preorder.length - 1,
                    postorder, 0, postorder.length - 1);
};

The code is very similar to the previous two problems. Let's think about why the binary tree reconstructed from preorder and postorder traversal results might not be unique.

The key lies in this line:

int leftRootVal = preorder[preStart + 1];

We assume that the second element in the preorder traversal is the root of the left subtree. However, the left subtree could actually be null, making this element the root of the right subtree instead. Since we can't determine this with certainty, the final result is not unique.

Thus, the problem of reconstructing a binary tree from preorder and postorder traversal results is resolved.

To echo the previous discussion, constructing a binary tree usually involves a "divide and conquer" approach: constructing the entire tree = root node + constructing the left subtree + constructing the right subtree. First, find the root node, then use the root node's value to identify the elements of the left and right subtrees, and recursively construct the left and right subtrees.

Do you now understand the subtlety of this process?

Related Problems

You can install my Chrome extension then open the link.

LeetCode	Difficulty
1008. Construct Binary Search Tree from Preorder Traversal	🟠

Binary Tree in Action (Construction)

105. 从前序与中序遍历序列构造二叉树 https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal

105. Construct Binary Tree from Preorder and Inorder Traversal https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal

106. 从中序与后序遍历序列构造二叉树 https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal

106. Construct Binary Tree from Inorder and Postorder Traversal https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal

654. 最大二叉树 https://leetcode.cn/problems/maximum-binary-tree

654. Maximum Binary Tree https://leetcode.com/problems/maximum-binary-tree

889. 根据前序和后序遍历构造二叉树 https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-postorder-traversal

889. Construct Binary Tree from Preorder and Postorder Traversal https://leetcode.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal

Constructing the Maximum Binary Tree

Constructing a Binary Tree from Preorder and Inorder Traversal

Constructing a Binary Tree from Postorder and Inorder Traversal Results

Constructing a Binary Tree from Postorder and Preorder Traversal Results