当前位置: 首页 > news >正文

Construct Binary Tree from Inorder and Postorder Traversal

题目:Given inorder and postorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

思路:

本题思路与之前的从前序遍历和中序遍历建立二叉树的思路一致,不再赘述。

可参考前一篇博客。链接地址。

代码:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        int posStart=0,preEnd=postorder.size()-1;
        int inStart=0,inEnd=inorder.size()-1;
        
        return constructHelper(postorder,posStart,preEnd,
                inorder, inStart, inEnd);
    }
    
    TreeNode* constructHelper(vector<int>&postorder,int posStart,int posEnd,
                vector<int>&inorder,int inStart,int inEnd){
        if(posStart>posEnd||inStart>inEnd)  return NULL;
        
        int val=postorder[posEnd];
        TreeNode*p =new TreeNode(val);
        int k=0;
        for(int i=0;i<inorder.size();i++){
            if(inorder[i]==val){
                k=i;break;//第k个
            } 
        }
        
        p->left= constructHelper(postorder,posStart,posStart+k-inStart-1,inorder, inStart,k-1);//k之前
                //k-start  考虑这种情况,在找到右子树的左子树的时候
                //k在右边,inStart也在右边,此时需要找的是左边的个数,
                //k-inStart 就解决了这个问题
        p->right=constructHelper(postorder,posStart+k-inStart , posEnd-1,inorder,k+1, inEnd); 
        return p;        
    }
};


转载于:https://www.cnblogs.com/jsrgfjz/p/8519838.html

相关文章:

  • Android学习笔记之Fragment的两种使用方法
  • Android学习笔记之SQLite数据库的使用及常用的增删改查方法、无sql语句的DRUD方法汇总
  • codeforces 455C 并查集
  • Android学习笔记之使用意图打开内置应用程序组件
  • java web sql注入测试(3)---现象分析
  • Android学习笔记之广播意图及广播接收者MyBroadcastReceiver、Broadcast
  • 一些简单的shell脚本实例 转
  • xUtils简介及其使用方法
  • OC基础(20)
  • Android框架Picasso介绍
  • Assets遇到的问题
  • 直接拿来用!最火的Android开源项目(一)
  • python --循环对象
  • Oracle中用触发器实现自动记录表数据被修改的历史信息
  • 直接拿来用!最火的Android开源项目(完结篇)
  • -------------------- 第二讲-------- 第一节------在此给出链表的基本操作
  • 自己简单写的 事件订阅机制
  • 78. Subsets
  • happypack两次报错的问题
  • linux安装openssl、swoole等扩展的具体步骤
  • react-native 安卓真机环境搭建
  • windows下使用nginx调试简介
  • 译米田引理
  • 赢得Docker挑战最佳实践
  • ​TypeScript都不会用,也敢说会前端?
  • ​香农与信息论三大定律
  • #控制台大学课堂点名问题_课堂随机点名
  • (32位汇编 五)mov/add/sub/and/or/xor/not
  • (4) PIVOT 和 UPIVOT 的使用
  • (C#)Windows Shell 外壳编程系列4 - 上下文菜单(iContextMenu)(二)嵌入菜单和执行命令...
  • (C++)八皇后问题
  • (翻译)Entity Framework技巧系列之七 - Tip 26 – 28
  • (论文阅读30/100)Convolutional Pose Machines
  • (学习日记)2024.03.12:UCOSIII第十四节:时基列表
  • (一)UDP基本编程步骤
  • (译)2019年前端性能优化清单 — 下篇
  • (转)德国人的记事本
  • *_zh_CN.properties 国际化资源文件 struts 防乱码等
  • .apk 成为历史!
  • .Net 4.0并行库实用性演练
  • .NET Core WebAPI中使用Log4net 日志级别分类并记录到数据库
  • .NET Core 通过 Ef Core 操作 Mysql
  • .NETCORE 开发登录接口MFA谷歌多因子身份验证
  • .net通用权限框架B/S (三)--MODEL层(2)
  • .NET项目中存在多个web.config文件时的加载顺序
  • .sys文件乱码_python vscode输出乱码
  • /deep/和 >>>以及 ::v-deep 三者的区别
  • /etc/sudoer文件配置简析
  • [AIR] NativeExtension在IOS下的开发实例 --- IOS项目的创建 (一)
  • [BZOJ 4129]Haruna’s Breakfast(树上带修改莫队)
  • [EULAR文摘] 利用蛋白组学技术开发一项蛋白评分用于预测TNFi疗效
  • [javaSE] GUI(事件监听机制)
  • [Kubernetes]9. K8s ingress讲解借助ingress配置http,https访问k8s集群应用
  • [LeetCode] NO. 387 First Unique Character in a String
  • [leetcode]Clone Graph