IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 【力扣106】 从中序与后续遍历序列构造二叉树的算法实现 -> 正文阅读

[数据结构与算法]【力扣106】 从中序与后续遍历序列构造二叉树的算法实现

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

?

方法:迭代
思路:

  • 迭代法是一种非常巧妙的实现方法。迭代法的实现基于以下两点发现。
  • 如果将中序遍历反序,则得到反向的中序遍历,即每次遍历右孩子,再遍历根节点,最后遍历左孩子。
  • 如果将后序遍历反序,则得到反向的前序遍历,即每次遍历根节点,再遍历右孩子,最后遍历左孩子。
  • 「反向」的意思是交换遍历左孩子和右孩子的顺序,即反向的遍历中,右孩子在左孩子之前被遍历

因此可以使用和「105. 从前序与中序遍历序列构造二叉树」的迭代方法类似的方法构造二叉树。

对于后序遍历中的任意两个连续节点 u?和 v(在后序遍历中,u 在 v 的前面),根据后序遍历的流程,我们可以知道 u 和 v 只有两种可能的关系:

  • u 是 v 的右儿子。这是因为在遍历到 u 之后,下一个遍历的节点就是 u 的双亲节点,即 v;
  • v 没有右儿子,并且 u 是 v 的某个祖先节点(或者 v 本身)的左儿子。如果 v 没有右儿子,那么上一个遍历的节点就是 v 的左儿子。如果 v 没有左儿子,则从 v 开始向上遍历 v 的祖先节点,直到遇到一个有左儿子(且 v 不在它的左儿子的子树中)的节点?

第二种关系看上去有些复杂。我们举一个例子来说明其正确性,并在例子中给出我们的迭代算法。

例子

我们以树

为例,它的中序遍历和后序遍历分别为

inorder = [15, 9, 10, 3, 20, 5, 7, 8, 4]
postorder = [15, 10, 9, 5, 4, 8, 7, 20, 3]

我们用一个栈 stack 来维护「当前节点的所有还没有考虑过左儿子的祖先节点」,栈顶就是当前节点。也就是说,只有在栈中的节点才可能连接一个新的左儿子。同时,我们用一个指针 index 指向中序遍历的某个位置,初始值为 n - 1,其中 n 为数组的长度。index 对应的节点是「当前节点不断往右走达到的最终节点」,这也是符合反向中序遍历的,它的作用在下面的过程中会有所体现。

首先我们将根节点 3 入栈,再初始化 index 所指向的节点为 4,随后对于后序遍历中的每个节点,我们依次判断它是栈顶节点的右儿子,还是栈中某个节点的左儿子。

?

class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if (postorder.size() == 0) {
            return nullptr;
        }
        auto root = new TreeNode(postorder[postorder.size() - 1]);
        auto s = stack<TreeNode*>();
        s.push(root);
        int inorderIndex = inorder.size() - 1;
        for (int i = int(postorder.size()) - 2; i >= 0; i--) {
            int postorderVal = postorder[i];
            auto node = s.top();
            if (node->val != inorder[inorderIndex]) {
                node->right = new TreeNode(postorderVal);
                s.push(node->right);
            } else {
                while (!s.empty() && s.top()->val == inorder[inorderIndex]) {
                    node = s.top();
                    s.pop();
                    inorderIndex--;
                }
                node->left = new TreeNode(postorderVal);
                s.push(node->left);
            }
        }
        return root;
    }
};

?

  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章           查看所有文章
加:2022-12-25 11:33:24  更:2022-12-25 11:38:45 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年5日历 -2024/5/25 12:04:08-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码