leetcode<105. 从前序与中序遍历序列构造二叉树><106. 从中序与后序遍历序列构造二叉树>

简介: 二叉树编程题解析

image.png

传送门:105. 从前序与中序遍历序列构造二叉树

给定一个二叉树的前序中序遍历,要求根据两个顺序构建一棵二叉树。对前中序遍历不够熟悉的同学可能会比较疑惑,甚至不知道该如何下手。前序遍历则是以根节点左节点右节点的顺序进行遍历,而中序遍历则是以左节点根节点右节点的顺序进行遍历。于是前序遍历的第一个节点便是这棵树的根节点,我们在中序遍历之中找这个节点的位置,此时在节点左边的节点都是根节点的左子树,右边的都是其右子树。

根据这个规律我们可以顺着前序遍历,不断排除已用过节点,将每次的范围抽象成一个个区间。每次都找到这个根的左子树和右子树,并将其连接起来。便完成树的构造。

TreeNode* _buildTree(vector<int>& preorder, vector<int>& inorder,int begin,int end,int& root)
    {
        if(begin>end) return nullptr;                       //区间内没有节点了就返回
        TreeNode* newnode = new TreeNode(preorder[root]);  //创建当前节点
        //在找中序中找位置
        int i;
        for(i = begin;i<=end;i++)
        {
            if(inorder[i] == preorder[root]) break;
        }
        root++; //标记位
        //将原数组分成三个部分 begin~i-1 ,i ,i+1~end
        newnode->left = _buildTree(preorder,inorder,begin,i-1,root); //连接左子树
        newnode->right = _buildTree(preorder,inorder,i+1,end,root);  //连接右子树
        return newnode;       //返回构建完的树
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int i = 0;            //以引用的方式记录节点的下标,因为每次找的都是不同的节点
        return _buildTree(preorder, inorder,0,preorder.size()-1,i);
    }

image.gif

image.png

传送门:106. 从中序与后序遍历序列构造二叉树

这题与上面一题本质上是一样的,但是在后序遍历中根节点为最后一位,因此要从后序遍历的最后一位开始遍历。不仅如此根节点的上一位并不是左节点而是右节点,因此在连接的时候必须要先连接右节点再连接左节点。

TreeNode* _buildTree(vector<int>& inorder, vector<int>& postorder,int& root,int begin,int end)
    {
        if(begin>end) return nullptr;  //区间内没数则返回
        TreeNode* newnode = new TreeNode(postorder[root]);
        int i;
        for(i = begin;i<=end;i++)       //找当前节点在中序遍历中的位置
        {
            if(inorder[i]==postorder[root]) break;
        }
        //分割区间
        // begin~i-1, i , i+1~end
        root--;    //向前遍历
        newnode->right = _buildTree(inorder,postorder,root,i+1,end); //连接右节点
        newnode->left = _buildTree(inorder,postorder,root,begin,i-1); //连接左节点
        return newnode;    //返回构造好的节点
    }
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        int i = postorder.size()-1;  //从末尾开始遍历
        return _buildTree(inorder,postorder,i,0,postorder.size()-1);
    }

image.gif

目录
相关文章
|
4月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
59 6
|
2月前
【LeetCode 31】104.二叉树的最大深度
【LeetCode 31】104.二叉树的最大深度
20 2
|
2月前
【LeetCode 29】226.反转二叉树
【LeetCode 29】226.反转二叉树
18 2
|
2月前
【LeetCode 28】102.二叉树的层序遍历
【LeetCode 28】102.二叉树的层序遍历
16 2
|
2月前
【LeetCode 43】236.二叉树的最近公共祖先
【LeetCode 43】236.二叉树的最近公共祖先
20 0
|
2月前
【LeetCode 38】617.合并二叉树
【LeetCode 38】617.合并二叉树
15 0
|
2月前
【LeetCode 37】106.从中序与后序遍历构造二叉树
【LeetCode 37】106.从中序与后序遍历构造二叉树
17 0
|
2月前
【LeetCode 34】257.二叉树的所有路径
【LeetCode 34】257.二叉树的所有路径
21 0
|
2月前
【LeetCode 32】111.二叉树的最小深度
【LeetCode 32】111.二叉树的最小深度
19 0
|
4月前
|
存储 算法
二叉树进阶-学会层序遍历助你一次刷完leetcode10道题
文章深入探讨了二叉树的层序遍历方法,并展示了如何通过队列实现层序遍历的算法逻辑,同时指出掌握层序遍历技巧可以帮助解决LeetCode上的多道相关题目。
二叉树进阶-学会层序遍历助你一次刷完leetcode10道题