• 首页

  • 文章归档

  • 文章分类

  • 日志

  • 图库

  • 友链

  • 留言板

  • 关于我
H i , m e g u m i
H i , m e g u m i

无名高

获取中...

09
25
算法题

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

发表于 2020-09-25 • 树 leetcode • 被 543 人看爆

根据一棵树的中序遍历与后序遍历构造二叉树。

注意:
你可以假设树中没有重复的元素。

例如,给出

中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]
返回如下的二叉树:

    3
   / \
  9  20
    /  \
   15   7

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


老题目了,已知后序遍历序列和前序遍历序列以后,都能够知道一棵树的根结点位置,前序遍历在序列第一个位置,后序遍历在序列第二个位置。
确定了根结点的位置和值以后,遍历中序遍历,比较中序遍历序列中与根结点值相同的值,就找到根结点在中序遍历的位置,此时中序遍历根结点左边即为左子树,右边即为右子树,递归的去查找左子树和右子树的根节点,并挂到根节点的左右孩子指针上即可。

代码:

class Solution {
public:
    /**
     根据中序和后序遍历构造二叉树 
     后序遍历的最后一个节点是树的根节点,根据这个查找到中序遍历的根节点
     
     **/
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        int size = (int)inorder.size();
        return getRoot(0, size-1, 0, size-1, inorder, postorder);
    }
    
    // 标记当前树在中序和后序的位置
    TreeNode* getRoot(int inLeft, int inRight, int postLeft, int postRight,
                      vector<int>& inorder, vector<int>& postorder){
        if (inLeft > inRight) {
            return nullptr;
        }
        int rootVal = postorder[postRight]; // 根节点的值
        int k = inLeft; // k指向根节点在中序的位置
        for (; k <= inRight; ++k) {// 查找在中序遍历的位置
            if (inorder[k] == rootVal) {
                break;
            }
        }
        TreeNode* tmp = new TreeNode(rootVal);
        int leftTreeNum = k - inLeft;
        tmp->left = getRoot(inLeft, k-1, postLeft, postLeft + leftTreeNum-1, inorder, postorder);
        tmp->right = getRoot(k+1, inRight, postLeft+leftTreeNum, postRight-1, inorder, postorder);
        return tmp;
    } 
};
分享到:
LeetCode 18.四数之和
LeetCode 501.二叉搜索中的众数
  • 文章目录
  • 站点概览
无名高

帅哥无名高

我们是如何走到这一步

Github QQ Email RSS
看爆 Top5
  • SpringBoot学习笔记 2,395次看爆
  • 解决在IDEA编写Java代码时,向数据库中插入中文字符后显示?乱码问题 2,324次看爆
  • JDBC核心技术笔记 2,204次看爆
  • SpringMVC学习笔记 1,907次看爆
  • MySQL基础学习笔记 1,859次看爆
粤公网安备 44030702003128号 黔ICP备20006240号

Copyright © 2022 无名高 ·

Proudly published with Halo · Theme by fyang · 站点地图