跳至主要內容

二叉树心法（构造篇）

labuladong原创数据结构二叉树分解问题的思路约 9507 字

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

剑指 Offer 07. 重建二叉树 https://leetcode.cn/problems/zhong-jian-er-cha-shu-lcof

剑指 Offer 07. 重建二叉树 LCOF https://leetcode.com/problems/zhong-jian-er-cha-shu-lcof

Info

已完成网站教程、网站习题、配套插件中所有多语言代码的校准，解决了之前 chatGPT 翻译可能出错的问题~

读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

LeetCodeDifficulty
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 should first learn:

This article is the second part following Guide to Binary Trees (Overview). Let’s first recap the key points from the previous article:

注

There are two main thinking patterns for solving binary tree problems:

1. Can you obtain the answer by traversing the binary tree once? If yes, use a traverse function along with external variables. This is called the "traverse" thinking pattern.

2. Can you define a recursive function to derive the answer from the subproblems (subtrees)? If yes, write the definition of this recursive function and make full use of its return value. This is called the "decompose the problem" thinking pattern.

Regardless of the thinking pattern, you need to consider:

If you isolate a single binary tree node, what does it need to do? When should it perform its task (pre-order, in-order, post-order)? Other nodes don’t require your concern; the recursive function will handle them.

The first article Guide to Binary Trees (Thinking Patterns) discussed "traverse" and "decompose the problem" thinking patterns. This article focuses on binary tree construction problems.

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

Let's dive into an example problem.

Constructing the Maximum Binary Tree

Let's start with a simple one, LeetCode Problem 654 "Maximum Binary Tree." The problem statement 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:

  1. Create a root node whose value is the maximum value in nums.
  2. Recursively build the left subtree on the subarray prefix to the left of the maximum value.
  3. 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);

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 subtrees
// 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;
}

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;
    }
}

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);

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);
}

In the previous article The Framework of Binary Trees, we discussed how the differences in traversal order lead to specific distributions of elements in the preorder and inorder arrays:

Finding the root node is straightforward. The first value in the preorder traversal, preorder[0], is the root node's value.

The key 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 arrays
    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;
}

For the rootVal and index variables in the code, it refers to the situation shown in the diagram below:

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

Since the problem states that the values of the binary tree nodes are unique, we can use a HashMap to store the mapping from elements to indices. This way, we can directly find the index corresponding to rootVal through 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);
    // ...
}

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, ?, ?);

The start and end indices of the inorder arrays for 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);

What about the preorder array? How do you determine the start and end indices for the left and right subarrays?

This can be deduced by the number of nodes in the left subtree. Assuming the number of nodes in the left subtree is leftSize, the indices in the preorder array would look like this:

Looking at this diagram, you can write down 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);

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;
    }
}

Our main function only needs to call the build function. While it may seem intimidating with so many parameters and lines of code, it is actually quite straightforward. These parameters mainly control the start and end positions of the array, which can be easily understood with a diagram.

Constructing a Binary Tree from Postorder and Inorder Traversal Results

Similar to the previous problem, this time we use the arrays from 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);

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

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);
}

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

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

The overall algorithm framework is very similar to the previous problem. We will still write a helper function 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;
    }
}

Now the states corresponding to postorder and inorder are as follows:

We can correctly fill in the indices at the question marks according to the above diagram:

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);

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

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;
    }
}

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);

This problem has a fundamental difference from the previous two problems:

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

The problem states that if there are multiple possible restoration results, you can return any one of them.

Why? The approach to constructing a binary tree is straightforward: first find the root node, then recursively construct the left and right subtrees.

In the previous two problems, you could find the root node using the preorder or postorder traversal results and then determine the left and right subtrees based on 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 know exactly which nodes belong to the left or right subtrees.

For example, given this input:

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

Both of the following trees meet the conditions, but they obviously have different structures:

That said, the logic to restore a binary tree from postorder and preorder traversal results is not much different from the previous two problems. It also involves controlling the indices of the left and right subtrees:

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

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

3. Find the value of the left subtree's root node in the postorder traversal result, thereby determining the index boundaries of the left subtree, and subsequently the index boundaries of the right subtree. 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 postorder[postStart..postEnd]
    // 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 left subtree
        // 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 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;
    }
}

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?

引用本文的题目

安装 我的 Chrome 刷题插件 点开下列题目可直接查看解题思路：

LeetCode力扣
1008. Construct Binary Search Tree from Preorder Traversal1008. 前序遍历构造二叉搜索树
-剑指 Offer 07. 重建二叉树
-剑指 Offer 33. 二叉搜索树的后序遍历序列
上次编辑于: