第一题 二叉树的锯齿形档次遍历
题目
解题思路
题目为一般的树的档次遍历
用广搜能够轻松的实现该题
具体思路与该题相似 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)。
//有应用空间存储哈希映射吗，为什么官解的复杂度剖析有提这个