Leetcode 106 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* dfs(vector<int>& preorder, int ps,int pe,vector<int>& inorder,int is,int ie)  
    {  
        if(ps>pe ) return NULL;  
        TreeNode* root=new TreeNode(preorder[pe]);  
        int pos;  
        for(int i=is;;i++)  
        if(inorder[i]==preorder[pe])  
        {  
            pos=ie-i;  
            break;  
        }  
        root->left=dfs(preorder,ps,pe-pos-1,inorder,is,ie-pos-1);  
        root->right=dfs(preorder,pe-pos,pe-1,inorder,ie-pos+1,ie);  
        return root;  
    }  
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        return dfs(postorder,0,inorder.size()-1,inorder,0,inorder.size()-1);
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏游戏杂谈

cocos2d-x 2.x版本接入bugly的总结

最开始项目使用的是自己DIY的很简陋的上报系统,后来改成google breakpad来上报,发现其实都做的不太理想,游戏引擎因为版本历史问题存在一些崩溃问题。...

21200
来自专栏WOLFRAM

by 骁君

14630
来自专栏Netkiller

网络测试,带宽测试,流量测试

节选自《Netkiller Testing 手札》网络测试章节 第 14 章 网络测试 目录 14.1. iperf3 - perform network t...

83740
来自专栏bboysoul

linux下的彩蛋和各种有趣的命令

循环输出 for ((i=1;i<=30;i++));do linux_logo -f -L $i;sleep 0.1;done

17040
来自专栏西安-晁州

golang代码片段(摘抄)

以下是从golang并发编程实战2中摘抄过来的代码片段,主要是实现一个简单的tcp socket通讯(客户端发送一个数字,服务端计算该数字的立方根然后返回),写...

27800
来自专栏Golang语言社区

GO语言 TCP传输实例

package main import ( "net" "fmt" ) var ( maxRead = 1100 msgStop = []byt...

35060
来自专栏机器学习从入门到成神

Spring与MyBatis的整合

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sinat_35512245/articl...

2.3K20
来自专栏无所事事者爱嘲笑

react-native 打开设置界面

51140
来自专栏无所事事者爱嘲笑

react-native 打开设置界面

50420
来自专栏xingoo, 一个梦想做发明家的程序员

MFC 随机矩形

问题描述:   简单地使用随即的尺寸和颜色不停的绘制一系列的图像。 一种古老的方式:   设置一个向窗口函数发送WM_TIMER消息的windows计时器。  ...

21650

扫码关注云+社区

领取腾讯云代金券