Leetcode: Construct Binary Tree from Preorder and Inorder Traversal

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

Note: You may assume that duplicates do not exist in the tree. 根据前序遍历和中序遍历结果构造二叉树。

思路分析: 分析二叉树前序遍历和中序遍历的结果我们发现: 二叉树前序遍历的第一个节点是根节点。 在中序遍历中找出根节点,由根节点分开,中序遍历左边是左子树中序遍历结果(设有X个节点),右边是右子树遍历结果(设有Y个节点)。 前序遍历除去第一个根节点,数X节点,这X个节点是左子树前序遍历的结果,剩下节点(肯定是Y个)是右子树前序遍历结果。 这样我们就得到了左右子树的前序遍历和中序遍历的结果了,所以又回到了原来的问题,这样我们自然想到了递归。 C++代码:

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution
{
private:
    TreeNode *makeNode(vector<int>::iterator preBegin, vector<int>::iterator preEnd, vector<int>::iterator inBegin, vector<int>::iterator inEnd)
    {
        if (preBegin == preEnd) return nullptr;
        //从中序遍历结果中找出根节点(根节点在前序遍历中是第一个节点)
        vector<int>::iterator itRoot = find(inBegin, inEnd, *preBegin);
        TreeNode *root = new TreeNode(*itRoot);
        //计算根的左子树节点个数
        int leftSize = itRoot - inBegin;
        //在中序遍历结果中根节点的左边是左子树中序遍历结果,右边是右子树中序遍历结果
        //在前序遍历结果中除去根节点前leftSize个节点是左子树前序遍历结果,后面的节点是右子树前序遍历结果
        root->left = makeNode(preBegin + 1, preBegin + leftSize + 1, inBegin, itRoot);
        root->right = makeNode(preBegin + leftSize + 1, preEnd, itRoot + 1, inEnd);
        return root;
    }
public:
    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder)
    {
        if (preorder.empty()) return nullptr;
        TreeNode *root = makeNode(preorder.begin(), preorder.end(), inorder.begin(), inorder.end());
        return root;
    }
};

其中find函数的签名如下:

template <class InputIterator, class T>
   InputIterator find (InputIterator first, InputIterator last, const T& val);

Find value in range
Returns an iterator to the first element in the range [first,last) that compares equal to val. If no such element is found, the function returns last.

The function uses operator== to compare the individual elements to val.

前面代码中vector::iterator这样的写法显得很冗长,我们采用C++模板的写法可以稍微简化下这样的写法(当然C++的template不是干这个用的)。此外,还可以使用typedef进行写法的简化。

class Solution
{
private:
    template <typename T>
    TreeNode *makeNode(T preBegin, T preEnd, T inBegin, T inEnd)
    {
        if (preBegin == preEnd) return nullptr;
        auto itRoot = find(inBegin, inEnd, *preBegin);
        TreeNode *root = new TreeNode(*itRoot);
        int leftSize = itRoot - inBegin;
        root->left = makeNode(preBegin + 1, preBegin + leftSize + 1, inBegin, itRoot);
        root->right = makeNode(preBegin + leftSize + 1, preEnd, itRoot + 1, inEnd);
        return root;
    }
public:
    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder)
    {
        if (preorder.empty()) return nullptr;
        TreeNode *root = makeNode(preorder.begin(), preorder.end(), inorder.begin(), inorder.end());
        return root;
    }
};

Java参考代码: 思路和上面一样,不过Java从数组中选择某个元素需要进行遍历(也可以转成List或者Set,但是遍历效率最高)上面C++代码中使用的是find函数。 有时候感觉C++代码还是挺简洁的!

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private TreeNode makeNode(int[] preorder, int preBegin, int preEnd, int[] inorder, int inBegin, int inEnd) {
        if (preBegin == preEnd) return null;
        int index = 0;
        for (int i = inBegin; i < inEnd; i++) {
            if (inorder[i] == preorder[preBegin]) {
                index = i;
            }
        }
        int leftSize = index - inBegin;
        TreeNode root = new TreeNode(preorder[preBegin]);
        root.left = makeNode(preorder, preBegin + 1, preBegin + leftSize + 1 , inorder, inBegin, inBegin + leftSize);
        root.right = makeNode(preorder, preBegin + leftSize + 1, preEnd, inorder, index + 1, inEnd);
        return root;
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length == 0) return null;
        TreeNode root = makeNode(preorder, 0, preorder.length ,inorder, 0, inorder.length);;
        return root;
    }
}

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏GreenLeaves

C# 多线程七之Parallel

关于Parallel不想说太多,因为它是Task的语法糖,至少我是这么理解的,官方文档也是这么说的,它本身就是基本Task的.假设我们有一个集合,不管是什么集合...

29640
来自专栏WebDeveloper

tendermint-peers讲解

Peer Exchange Reactor (PEX)确保与好的peers进行连接和通信

12840
来自专栏吴伟祥

一分钟上手Rinetd——端口转发工具 原

iptables 的功能当然强大,但理解与设置却有点抽象,便通过google认识了rinetd。

15320
来自专栏吴裕超

手机锁屏js倒计时停止问题解决办法探索

如图,有这么个需求,测试人员在测试过程中提了一个bug,手机锁屏再唤醒倒计时时间没有更新,仍从锁屏的时间继续,于是开始寻找解决之法

54330
来自专栏Java架构

十年Java架构师大厂实战(年薪80W)

BAT一直是程序员心神向往的地方,那些最最前沿的一线互联网技术都出自这些合称为大厂的地方,那里人才济济,哪怕实战经验不好的程序员进了那里,都会受到技术的熏陶,培...

21120
来自专栏一枝花算不算浪漫

GuavaCache学习笔记二:Java四大引用类型回顾

上一篇已经讲了,如何自己实现一个LRU算法。但是那种只是最基本的实现了LRU的剔除策略,并不能在生产中去使用。因为Guava Cache中使用的是SoftRef...

12830
来自专栏二进制文集

ThreadLocal 源码分析

ThreadLocal类中有一个threadLocalHashCode,作为ThreadLocalMap中key(ThreadLocal)的哈希值。

10720
来自专栏linux驱动个人学习

启动期间的内存管理之pagging_init初始化分页机制--Linux内存管理(十四)

在初始化内存的结点和内存区域之前, 内核先通过pagging_init初始化了内核的分页机制.

17720
来自专栏GreenLeaves

C# 多线程六之Task(任务)三之任务工厂

前面两篇关于Task的随笔,C# 多线程五之Task(任务)一 和 C# 多线程六之Task(任务)二,介绍了关于Task的一些基本的用法,以及一些使用的要点,...

13620
来自专栏linux驱动个人学习

启动期间的内存管理之build_zonelists初始化备用内存域列表zonelists--Linux内存管理(十三)

我们之前讲了在memblock完成之后, 内存初始化开始进入第二阶段, 第二阶段是一个漫长的过程, 它执行了一系列复杂的操作, 从体系结构相关信息的初始化慢慢向...

31140

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励