教程集 > Golang编程 > golang教程 > 正文面试题07. 重建二叉树 Golang

面试题07. 重建二叉树 Golang

发布时间：2021-12-04 编辑：jiaochengji.com

教程集为您提供面试题07. 重建二叉树 Golang等资源，欢迎您收藏本站，我们将为您提供最新的面试题07. 重建二叉树 Golang资源

<svg xmlns="http://www.w3.org/2000/svg" style="display: none;"><path stroke-linecap="round" d="M5,0 0,2.5 5,5z" id="raphael-marker-block" style="-webkit-tap-highlight-color: rgba(0, 0, 0, 0);"/></svg><h1>面试题07. 重建二叉树</h1>

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

例如，给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：

. 3
. / \
9 20
… / \
…15 7。

限制：

0 <= 节点个数 <= 5000

<h2>思路</h2>

中序遍历就是把树拍扁得到的数组，前序遍历的第一个节点就是这个树的根节点。
根据这个根节点可以把中序遍历拆分为左右子树的中序遍历。
然后通过递归把左右子树的根节点拎出来，最终重构二叉树。

<h2>我的解答</h2> <pre><code class="lang-go hljs"><span class="token keyword">func</span> <span class="token function">buildTree</span><span class="token punctuation">(</span>preorder <span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token builtin">int</span><span class="token punctuation">,</span> inorder <span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token builtin">int</span><span class="token punctuation">)</span> <span class="token punctuation">(</span>Head <span class="token operator">*</span>TreeNode <span class="token punctuation">)</span><span class="token punctuation">{</span> <span class="token keyword">if</span> <span class="token function">len</span><span class="token punctuation">(</span>inorder<span class="token punctuation">)</span><span class="token operator">==</span><span class="token number">0</span><span class="token punctuation">{</span> <span class="token keyword">return</span> <span class="token boolean">nil</span> <span class="token punctuation">}</span> <span class="token keyword">for</span> <span class="token boolean">_</span><span class="token punctuation">,</span>vp<span class="token operator">:=</span><span class="token keyword">range</span> preorder<span class="token punctuation">{</span> <span class="token keyword">for</span> ii<span class="token punctuation">,</span>vi<span class="token operator">:=</span><span class="token keyword">range</span> inorder<span class="token punctuation">{</span> <span class="token keyword">if</span> vp<span class="token operator">==</span>vi<span class="token punctuation">{</span> Left<span class="token operator">:=</span><span class="token function">buildTree</span><span class="token punctuation">(</span>preorder<span class="token punctuation">,</span>inorder<span class="token punctuation">[</span><span class="token punctuation">:</span>ii<span class="token punctuation">]</span><span class="token punctuation">)</span> Right<span class="token operator">:=</span><span class="token function">buildTree</span><span class="token punctuation">(</span>preorder<span class="token punctuation">,</span>inorder<span class="token punctuation">[</span>ii<span class="token operator"> </span><span class="token number">1</span><span class="token punctuation">:</span><span class="token punctuation">]</span><span class="token punctuation">)</span> Head<span class="token operator">:=</span> <span class="token operator">&</span>TreeNode<span class="token punctuation">{</span> Val<span class="token punctuation">:</span>vp<span class="token punctuation">,</span> Left<span class="token punctuation">:</span>Left<span class="token punctuation">,</span> Right<span class="token punctuation">:</span>Right<span class="token punctuation">,</span> <span class="token punctuation">}</span> <span class="token keyword">return</span> Head <span class="token punctuation">}</span> <span class="token punctuation">}</span> <span class="token punctuation">}</span> <span class="token keyword">return</span> <span class="token punctuation">}</span> </code></pre>

<blockquote class="layui-elem-quote" style="width: 100%;overflow:hidden"> 作者： Cyan1956
链接： https://blog.csdn.net/Cyan1956/article/details/104638859
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
</blockquote>

到此这篇关于“面试题07. 重建二叉树 Golang”的文章就介绍到这了,更多文章或继续浏览下面的相关文章，希望大家以后多多支持JQ教程网！

您可能感兴趣的文章：
面试题07. 重建二叉树 Golang
数据结构-树和二叉树(Golang)
数据结构中树与二叉树基础算法的比较
 关于二叉树的深度算法题目及解答
 数据结构和算法(Golang实现)(29)查找算法-2-3树和左倾红黑树
 golang sdk后端怎么用_Golang资深后端工程师需要了解的知识点
 golang实现常用集合原理介绍
 Python中的二叉排序树和平衡二叉树是什么
 go 面试题
 C 实现二叉查找树过程详解教程【图】

上一篇：【GoLang】golang底层数据类型实现原理下一篇：golang 释放内存机制的探索

[关闭]

最近更新

浏览排行

~ ~