二叉树构造算法详解：四种遍历方式下的二叉树构建方法

二叉树构造算法详解：四种遍历方式下的二叉树构建方法

引用

CSDN

1.

https://m.blog.csdn.net/weixin_42445439/article/details/141113238

二叉树的构造是计算机科学中的一个基础且重要的概念。本文将带领大家解决根据各种遍历方式构造二叉树的算法问题，包括最大二叉树、从前序与中序遍历序列构造二叉树、从中序与后序遍历序列构造二叉树以及根据前序和后序遍历构造二叉树。

二叉树构造的基本思路

构造完整的二叉树可以分解为递归构造根节点、左子树和右子树。这种分解问题的方法是解决二叉树构造问题的核心思路。

1. 最大二叉树

题目描述

给定一个不重复的整数数组 nums。最大二叉树可以用下面的算法从 nums 递归地构建：

1. 创建一个根节点，其值为 nums 中的最大值。
2. 递归地在最大值左边的子数组前缀上构建左子树。
3. 递归地在最大值右边的子数组后缀上构建右子树。

返回 nums 构建的最大二叉树。

输入：nums = [3,2,1,6,0,5]
输出：[6,3,5,null,2,0,null,null,1]

解释：递归调用如下所示：

• [3,2,1,6,0,5] 中的最大值是 6，左边部分是 [3,2,1]，右边部分是 [0,5]。
• [3,2,1] 中的最大值是 3，左边部分是 []，右边部分是 [2,1]。
• 空数组，无子节点。
• [2,1] 中的最大值是 2，左边部分是 []，右边部分是 [1]。
• 空数组，无子节点。
• 只有一个元素，所以子节点是一个值为 1 的节点。
• [0,5] 中的最大值是 5，左边部分是 [0]，右边部分是 []。
• 只有一个元素，所以子节点是一个值为 0 的节点。
• 空数组，无子节点。

解法与思路

要解决这个问题，我们需要：

1. 找到每次递归传入数组的最大值作为根节点。
2. 该最大值下标左边的元素递归构造为左子树，右边的元素递归构造为右子树。

下面是具体的代码实现：

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number[]} nums
 * @return {TreeNode}
 */
var constructMaximumBinaryTree = function(nums) {
    return build(nums)
    function build(nums){
        if(nums.length === 0){
            return null
        }
        // 找到最大值 和 最大索引值
        let root = Math.max(...nums)
        let index = nums.indexOf(root)
        // 用最大值创建索引
        let rootNode = new TreeNode(root)
        // 最大值左侧为左子树
        rootNode.left = build(nums.slice(0,index))
        // 最大值右侧为左子树
        rootNode.right = build(nums.slice(index+1,nums.length))
        return rootNode
    }
};

2. 从前序与中序遍历序列构造二叉树

题目描述

给定两个整数数组 preorder 和 inorder，其中 preorder 是二叉树的先序遍历，inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

解法与思路

1. 找到根节点
2. 从遍历数组中找到左子树，递归构造左子树
3. 从遍历数组中找到右子树，递归构造右子树

根节点其实就是前序遍历数组的第一个元素。

下面是具体的代码实现：

// 函数签名分别 传入 前序遍历数组、中序遍历数组、前序遍历起始下标、中序遍历起始下表、尾标
function build(preorder, inorder, preStart, inStart, inEnd) {
    if (inStart > inEnd) {
        return null;
    }
    // 从前序遍历中找到根节点
    let root = preorder[preStart];
    // 中序遍历中找到根节点位置
    let rootIndex = inorder.indexOf(root);
    // 构造右子树时，前序遍历需要知道左子树长度
    let leftSize = rootIndex - inStart;
    // 构造根节点
    let rootNode = new TreeNode(root);
    // 构造左右子树
    rootNode.left = build(preorder, inorder, preStart + 1, inStart, rootIndex - 1);
    rootNode.right = build(preorder, inorder, preStart + leftSize + 1, rootIndex + 1, inEnd);
    return rootNode;
}

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
var buildTree = function(preorder, inorder) {
    return build(preorder, inorder, 0, 0, inorder.length - 1);
};

3. 从中序与后序遍历序列构造二叉树

题目描述

给定两个整数数组 inorder 和 postorder，其中 inorder 是二叉树的中序遍历，postorder 是同一棵树的后序遍历，请你构造并返回这颗二叉树。

解法与思路

这道题与上一道题的区别在于找根节点的过程变成了后序遍历的最后一个元素，和左右子树的索引稍有变动，剩下的思路可以说是一模一样。

下面是具体的代码实现：

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number[]} inorder
 * @param {number[]} postorder
 * @return {TreeNode}
 */
var buildTree = function(inorder, postorder) {
    return build(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
    function build(inorder, inStart, inEnd, postorder, postStart, postEnd) {
        if (inStart > inEnd) {
            return null;
        }
        // 后续遍历的最后一个便是根节点
        let root = postorder[postEnd];
        // 找到根节点在中序遍历中的位置
        let rootIndex = inorder.indexOf(root);
        // 后续遍历左子树起点需要左子树长度，左子树长度需要在前序遍历中获得
        let leftSize = rootIndex - inStart;
        // 构造根节点
        let rootNode = new TreeNode(root);
        // 递归构造左右子树
        rootNode.left = build(inorder, inStart, rootIndex - 1, postorder, postStart, postStart + leftSize - 1);
        rootNode.right = build(inorder, rootIndex + 1, inEnd, postorder, postStart + leftSize, postEnd - 1);
        return rootNode;
    }
};

4. 根据前序和后序遍历构造二叉树

题目描述

给定两个整数数组，preorder 和 postorder，其中 preorder 是一个具有无重复值的二叉树的前序遍历，postorder 是同一棵树的后序遍历，重构并返回二叉树。如果存在多个答案，可以返回其中任何一个。

解法与思路

本题最大的不同就在于只有根节点是确定的，而左右子树是不确定的，因此有多个解，题目也只要求返回任何一个即可。

下面是具体的代码实现：

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number[]} preorder
 * @param {number[]} postorder
 * @return {TreeNode}
 */
var constructFromPrePost = function(preorder, postorder) {
    return build(preorder, 0, preorder.length - 1, postorder, 0, postorder.length - 1);
    function build(preorder, preStart, preEnd, postorder, postStart, postEnd) {
        if (preStart > preEnd) {
            return null;
        }
        // 因为找左子树起点时使用了preorder[preStart+1]，当preStart = preEnd时还剩下一个节点
        if (preStart == preEnd) {
            return new TreeNode(preorder[preStart]);
        }
        // 找到根节点
        let rootVal = preorder[preStart];
        // 找到左子树起点在后续遍历中的位置
        let leftStartIndex = postorder.indexOf(preorder[preStart + 1]);
        // 左子树长度
        let size = leftStartIndex - postStart + 1;
        let root = new TreeNode(rootVal);
        root.left = build(preorder, preStart + 1, preStart + size, postorder, postStart, leftStartIndex);
        root.right = build(preorder, preStart + size + 1, preEnd, postorder, leftStartIndex + 1, postEnd);
        return root;
    }
};

小结

通过以上四种构造二叉树的方法，我们可以总结出一个通用的思路：

1. 找到根节点的索引
2. 根据根节点索引找到左右子树的边界
3. 递归构造左右子树

这种分解问题的方法是解决二叉树构造问题的核心思路。