共计 1407 个字符,预计需要花费 4 分钟才能阅读完成。
第一题 二叉树的锯齿形档次遍历
题目
解题思路
题目为一般的树的档次遍历
用广搜能够轻松的实现该题
具体思路与该题相似 https://segmentfault.com/a/11…
区别只是在于
退出了对从左到右与从右到左的判断
代码
变量介绍
queue:双端队列
level:以后遍历所在的档次
q:保留以后队列的数据
val:数组切片,每遍历一层节点由它带回该层的数据,若为奇数,则反转
具体代码
func zigzagLevelOrder(root *TreeNode) (ans [][]int) {
if root == nil {return}
queue := []*TreeNode{root}
for level := 0; len(queue) > 0; level++ {vals := []int{}
q := queue
queue = nil
// 遍历队列 q 生成下一层的节点队列,并且将以后队列的值退出 val 数组筹备输入
for _, node := range q {vals = append(vals, node.Val)
if node.Left != nil {queue = append(queue, node.Left)
}
if node.Right != nil {queue = append(queue, node.Right)
}
}
// 实质上和层序遍历一样,咱们只须要把奇数层的元素翻转即可
if level%2 == 1 {for i, n := 0, len(vals); i < n/2; i++ {vals[i], vals[n-1-i] = vals[n-1-i], vals[i]
}
}
ans = append(ans, vals)
}
return
}
复杂度剖析
工夫复杂度:O(N),其中 N 为二叉树的节点数。每个节点会且仅会被遍历一次。
空间复杂度:O(N)。咱们须要保护存储节点的队列和存储节点值的双端队列,空间复杂度为 O(N)。
第二题 从前序与中序遍历序列结构二叉树
题目
解题思路
因为先序遍历的程序为根节点 - 左子树 - 右子树
先序遍历的第一个节点必然为根节点
preorder 和 inorder 均无反复元素
中序遍历的程序为左子树 - 根节点 - 右子树
因而咱们能够在中序遍历序列中失去被根节点划分进去的两个子树
再回到先序遍历中找到这两个子树持续进行结构操作
由此可见
递归是解决这道题的最不便的方法
代码
func buildTree(preorder []int, inorder []int) *TreeNode {if len(preorder) == 0 {return nil}
// 根节点
root := &TreeNode{preorder[0], nil, nil}
i := 0
// 在中序遍历序列中找到根节点
for ; i < len(inorder); i++ {if inorder[i] == preorder[0] {break}
}
// 结构左子树和右子树
root.Left = buildTree(preorder[1:len(inorder[:i])+1], inorder[:i])
root.Right = buildTree(preorder[len(inorder[:i])+1:], inorder[i+1:])
return root
}
复杂度剖析
工夫复杂度:O(n),其中 n 是树中的节点个数。
空间复杂度:O(n),除去返回的答案须要的 O(n) 空间之外,以及 O(h)(其中 h 是树的高度)的空间示意递归时栈空间。这里 h<n,所以总空间复杂度为 O(n)。
// 有应用空间存储哈希映射吗,为什么官解的复杂度剖析有提这个
正文完