LeetCode Construct Binary Tree from Traversal

最新推荐文章于 2024-01-17 16:19:42 发布

SegmentFault_

最新推荐文章于 2024-01-17 16:19:42 发布

阅读量451

点赞数

分类专栏： leetcode 数据结构与算法文章标签： leetcode 二叉树遍历

本文链接：https://blog.csdn.net/Programmer_acu/article/details/52664054

版权

数据结构与算法同时被 2 个专栏收录

8 篇文章

订阅专栏

leetcode

6 篇文章

订阅专栏

本文介绍如何通过前序遍历与中序遍历、中序遍历与后序遍历来构建二叉树的方法。首先根据前序遍历确定根节点，并在中序遍历中找到根节点位置以划分左右子树；再利用后序遍历的最后一个元素作为根节点，通过中序遍历来划分左右子树。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

1.Construct Binary Tree from Preorder and Inorder Traversal

根据二叉树前序遍历和中序遍历构造一颗二叉树。

现在有前序遍历4213769，中序遍历为1234679。根据前序和中序遍历的概念，构造一棵二叉树如下步骤：

(1) 设前序遍历的下标为prebegin = 0，preend = preorder.size() - 1。中序遍历下标inbegin = 0，inend = inorder.size() - 1。

(2) 以prebegin下标对应的元素为根节点，从中序遍历寻找该根节点。

(3) 在中序遍历中找到该根节点距离inbegin的偏移量rootin，rootin表示该根节点的左子树节点个数。左边为其左子树，右边为其右子树。inend = inbegin + rootin - 1，这样从inbegin到inend为prebegin对应根结点的左子树。然后prebegin + 1。

(4) 当prebegin > preend时，表明此时将上一次prebegin的根节点的左子树构建完毕。现在寻找其右子树，在中序遍历中，上一次寻找左子树完毕的根节点下标为inbegin + rootin，所以其右子树为的根节点为inbegin + rootin + 1。在前序遍历中，inbegin + rootin + 1对应的下标为prebegin + rootin + 1。

(5) 重复(2), (3),(4) 步骤。

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return CreatBinaryTree(preorder, inorder, 0, preorder.size() - 1, 0, inorder.size() - 1);
    }
    
    TreeNode* CreatBinaryTree(vector<int>& preorder, vector<int>& inorder, int prebegin, int preend, int inbegin, int inend) {
        
        if (prebegin > preend) {
            return NULL;
        }       
        
        int rootval = preorder[prebegin];
        TreeNode* root = new TreeNode(rootval);
        int rootin = 0;
        while (rootin <= inend && inorder[inbegin + rootin] != rootval) {
            ++rootin;
        }

        root -> left = CreatBinaryTree(preorder, inorder, prebegin + 1, prebegin + rootin, inbegin, inbegin + rootin - 1);
        root -> right = CreatBinaryTree(preorder, inorder, prebegin + rootin + 1, preend, inbegin + rootin + 1, inend);
        return root;
    }
};

2.Construct Binary Tree from Inorder and Postorder Traversal

根据二叉树的中序和后序遍历构造二叉树

现有中序遍历1234679，后序遍历1234679。

(1) 中序遍历下标inbegin = 0，inend = inorder.size() - 1，后序遍历下标为postbegin = 0，postend = postorder.size() - 1。

(2) 从后序遍历postend为根节点，在中序遍历寻找此根节点。

(3) 在中序遍历找到根节点，rootin记录postend根节点右子树节点个数。先寻找右子女，inbegin = inend - rootin + 1，从inbegin到inend为postend根节点的右子树。然后postend - 1，postbegin = postend - rootin，重复上述过程。

(4) 寻找右子女如果postbegin > postend，表明该右子女为NULL，然后寻找该右子女对应根结点的左子女，由于该根节点的为inend - rootin，左边为该根节点的左子树，inend = inend - rootin - 1，postend = postend - rootin - 1。因为rootin为postend右子树节点的个数，因此postend左子树的第一个根节点为postend - rootin - 1。

(5) 重复上述过程。

class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        return buildTree(inorder, postorder, 0, inorder.size() - 1, 0, postorder.size() - 1);
    }
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder, int inbegin, int inend, int postbegin, int postend) {
        if (postbegin > postend) {
            return NULL;
        }
        
        int rootval = postorder[postend];
        TreeNode* root = new TreeNode(rootval);
        int rootin = 0;
        while(rootin <= inend && inorder[inend - rootin] != rootval) {
            ++rootin;
        }
        
        root -> right = buildTree(inorder, postorder, inend - rootin + 1, inend, postend - rootin, postend - 1);
        root -> left = buildTree(inorder, postorder, inbegin, inend - rootin - 1, postbegin, postend - rootin - 1);
        return root;
    }
};