【力扣】根据二叉树的前序和中序遍历结果还原该二叉树(以及后序和中序还原)

简介: 【力扣】根据二叉树的前序和中序遍历结果还原该二叉树(以及后序和中序还原)

一 前序和中序还原二叉树


连接:根据二叉树的前序和中序遍历结果还原该二叉树


1f5df6e36027435fa6bb08fa4d7950ca.png


思路是这样的:


这个算法的目的是根据前序遍历和中序遍历的结果,重建一棵二叉树。

前序遍历的特点是,第一个元素一定是根节点,后面的元素是左子树和右子树的前序遍历。

中序遍历的特点是,根节点在左子树和右子树的中间,左边的元素是左子树的中序遍历,右边的元素是右子树的中序遍历。

因此,我们可以利用前序遍历确定根节点,然后在中序遍历中找到根节点的位置,从而分割出左子树和右子树的区间。

然后,我们递归地对左子树和右子树进行同样的操作,直到区间为空或者只有一个元素为止。

最后,我们返回重建好的二叉树的根节点。


代码并加上了注释:

class Solution { 
public: 
  //后序确定根 
  //中序分割左右区间 
  TreeNode* _buildTree(vector<int>& inorder, vector<int>& postorder, int& posti, int ibegin, int iend) { 
    if (ibegin > iend) return nullptr; //如果中序区间为空,返回空指针
    TreeNode* root = new TreeNode(postorder[posti]); //创建根节点,值为后序遍历的最后一个元素
    //分割左右子区间 
    int rooti = ibegin; //找到根节点在中序遍历中的位置
    while (rooti <= iend) { 
      if (inorder[rooti] == postorder[posti]) break; //找到了,跳出循环
      else rooti++; //没找到,继续向右移动
    } 
    --posti; //后序遍历的索引向前移动一位
    root->right = _buildTree(inorder, postorder, posti, rooti+1, iend); //递归构建右子树,中序区间为[rooti+1, iend]
    root->left = _buildTree(inorder, postorder, posti, ibegin, rooti-1); //递归构建左子树,中序区间为[ibegin, rooti-1]
    return root; //返回根节点
  } 
  TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) { 
    int i = postorder.size()-1; //初始化后序遍历的索引为最后一位
    return _buildTree(inorder, postorder, i, 0, inorder.size()-1); //调用辅助函数,中序区间为[0, inorder.size()-1]
  } 
};

二 后序和中序还原二叉树


如果是后序和中序让你来还原二叉树呢?

链接:后序和中序还原二叉树


还是上面那种思路,只不过这次要先递归构建右子树,这是因为后序遍历的特点是,最后一个元素是根节点,前面的元素是左子树和右子树的后序遍历,而且右子树在左子树的后面。所以,我们要先递归构建右子树,然后再构建左子树,这样才能保证后序遍历的索引正确。

59b611d4f5fe40a1b1af57d4961db3d4.png

后序遍历的最后一个元素是二叉树的根节点。

在中序遍历中找到根节点的位置,根节点左边的序列是左子树的中序遍历,右边的序列是右子树的中序遍历。

在后序遍历中找到对应的左子树和右子树的序列,左子树的长度和中序遍历中左子树的长度相同,右子树也一样。

递归地对左子树和右子树重复上述步骤,直到后序遍历或中序遍历为空。

例如,给定后序遍历 [9, 15, 7, 20, 3] 和中序遍历 [9, 3, 15, 20, 7],还原二叉树的过程如下:


后序遍历的最后一个元素是 3,它是二叉树的根节点。

在中序遍历中找到 3 的位置,它左边的序列 [9] 是左子树的中序遍历,右边的序列 [15, 20, 7] 是右子树的中序遍历。

在后序遍历中找到对应的左子树和右子树的序列,左子树只有一个元素 [9],右子树有三个元素 [15, 7, 20]。

对左子树递归地还原二叉树,由于后序遍历和中序遍历只有一个元素,所以左子节点就是 9。

对右子树递归地还原二叉树,由于后序遍历和中序遍历都不为空,重复上述步骤。


代码:

class Solution { 
public: 
  //后序确定根 
  //中序分割左右区间 
  TreeNode* _buildTree(vector<int>& inorder, vector<int>& postorder, int& posti, int ibegin, int iend) { 
    if (ibegin > iend) return nullptr; //如果中序区间为空,返回空指针
    TreeNode* root = new TreeNode(postorder[posti]); //创建根节点,值为后序遍历的最后一个元素
    //分割左右子区间 
    int rooti = ibegin; //找到根节点在中序遍历中的位置
    while (rooti <= iend) { 
      if (inorder[rooti] == postorder[posti]) break; //找到了,跳出循环
      else rooti++; //没找到,继续向右移动
    } 
    --posti; //后序遍历的索引向前移动一位
    root->right = _buildTree(inorder, postorder, posti, rooti+1, iend); //递归构建右子树,中序区间为[rooti+1, iend]
    root->left = _buildTree(inorder, postorder, posti, ibegin, rooti-1); //递归构建左子树,中序区间为[ibegin, rooti-1]
    return root; //返回根节点
  } 
  TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) { 
    int i = postorder.size()-1; //初始化后序遍历的索引为最后一位
    return _buildTree(inorder, postorder, i, 0, inorder.size()-1); //调用辅助函数,中序区间为[0, inorder.size()-1]
  } 
};


本节完

相关文章
|
1月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
40 6
|
1月前
|
存储 算法
二叉树进阶-学会层序遍历助你一次刷完leetcode10道题
文章深入探讨了二叉树的层序遍历方法,并展示了如何通过队列实现层序遍历的算法逻辑,同时指出掌握层序遍历技巧可以帮助解决LeetCode上的多道相关题目。
二叉树进阶-学会层序遍历助你一次刷完leetcode10道题
|
1月前
|
算法 Java
LeetCode第94题二叉树的中序遍历
文章介绍了LeetCode第94题"二叉树的中序遍历"的解法,使用递归实现了中序遍历的过程,遵循了"左根右"的遍历顺序,并提供了清晰的Java代码实现。
LeetCode第94题二叉树的中序遍历
|
1月前
|
索引 Python
【Leetcode刷题Python】从列表list中创建一颗二叉树
本文介绍了如何使用Python递归函数从列表中创建二叉树,其中每个节点的左右子节点索引分别是当前节点索引的2倍加1和2倍加2。
34 7
|
1月前
|
算法 Python
【Leetcode刷题Python】剑指 Offer 33. 二叉搜索树的后序遍历序列
本文提供了一种Python算法,用以判断给定整数数组是否为某二叉搜索树的后序遍历结果,通过识别根节点并递归验证左右子树的值是否满足二叉搜索树的性质。
14 3
|
1月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - II. 从上到下打印二叉树 II
本文提供了一种Python实现方法,用于层次遍历二叉树并按层打印结果,每层节点按从左到右的顺序排列,每层打印到一行。
28 3
|
1月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - I. 从上到下打印二叉树
本文介绍了使用Python实现从上到下打印二叉树的解决方案,采用层次遍历的方法,利用队列进行节点的访问。
28 2
|
1月前
|
Python
【Leetcode刷题Python】257. 二叉树的所有路径
LeetCode第257题"二叉树的所有路径"的Python语言解决方案,通过深度优先搜索算法来找到并返回所有从根节点到叶子节点的路径。
20 2
|
1月前
|
存储 算法 Java
LeetCode经典算法题:二叉树遍历(递归遍历+迭代遍历+层序遍历)以及线索二叉树java详解
LeetCode经典算法题:二叉树遍历(递归遍历+迭代遍历+层序遍历)以及线索二叉树java详解
60 0
|
1月前
|
算法 Java
LeetCode初级算法题:子数组最大平均数+二叉树的最小深度+最长连续递增序列+柠檬水找零
LeetCode初级算法题:子数组最大平均数+二叉树的最小深度+最长连续递增序列+柠檬水找零
32 0