Leetcode Golang 105. Construct Binary Tree from Preorder and Inorder Traversal.go

版权声明:原创勿转 https://blog.csdn.net/anakinsun/article/details/88935501

思路

根据前序遍历和中序遍历的结果数组,重新构建二叉树

前序的第一个元素就是数的root节点,从中序中找到根节点,则左边的都是左子树,右边的都是右子树

然后递归

code

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func buildTree(preorder []int, inorder []int) *TreeNode {
	if len(preorder) == 0 {
		return nil
	}
	res := &TreeNode{
		Val: preorder[0],
	}
	if len(preorder) == 1 {
		return res
	}
	idx := func(val int, nums []int) int {
		for i, v := range nums {
			if v == val {
				return i
			}
		}
		return -1
	}(res.Val, inorder)
	if idx == -1 {
		return nil
	}
	res.Left = buildTree(preorder[1:idx+1], inorder[:idx])
	res.Right = buildTree(preorder[idx+1:], inorder[idx+1:])
	return res
}

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏跟着阿笨一起玩NET

解决winform中mdi子窗体加载时显示最大化最小化按钮的方法

场景:在mid加载子窗体的时候如果指定WindowState为Maximized,加载完成后主窗体会显示最大化、最小化、关闭的按钮图标。

7830
来自专栏跟着阿笨一起玩NET

WinForm MDIParent如何防止重复打开

DI,全称是多文档界面(Multiple Document Interface),主要应用于基于图形用户界面的系统中。其目的是同时打开和显示多个文档,便于参考和...

13720
来自专栏JetpropelledSnake

Docker学习笔记之常见 Dockerfile 使用技巧

在掌握 Dockerfile 的基本使用方法后,我们再来了解一些在开发中使用 Dockerfile 的技巧。这一小节的展现方式与之前的略有不同,其主要来自阅读收...

21040
来自专栏chenjx85的技术专栏

leetcode-35- Search Insert Position

Given a sorted array and a target value, return the index if the target is found...

9130
来自专栏Kevin-ZhangCG

数据结构之链表解析

  我们知道,数组作为数据存储结构有一定的缺陷。在无序数组中,搜索时低效的;而在有序数组中,插入效率又很低;不管在哪一种数组中删除效率都很低。况且一个数组创建后...

13340
来自专栏跟着阿笨一起玩NET

C#模板引擎NVelocity实战项目演练

18430
来自专栏chenjx85的技术专栏

leetcode-581-Shortest Unsorted Continuous Subarray

Given an integer array, you need to find one continuous subarray that if you onl...

10540
来自专栏chenjx85的技术专栏

leetcode-599-Minimum Index Sum of Two Lists

Suppose Andy and Doris want to choose a restaurant for dinner, and they both hav...

8330
来自专栏跟着阿笨一起玩NET

C# 文本框 TextChanged 延时触发

25520
来自专栏Nian糕的私人厨房

JavaScript 通过简写增加代码可读性

行文过程中出现错误或不妥之处在所难免,希望大家能够给予指正,以免误导更多人,最后,如果你觉得我的文章写的还不错,希望能够点一下喜欢和关注,为了我能早日成为简书优...

10470

扫码关注云+社区

领取腾讯云代金券

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