乐趣区

关于golang:golangleetcode中级二叉树的锯齿形层次遍历从前序与中序遍历序列构造二叉树

jiezi

第一题 二叉树的锯齿形档次遍历

题目

解题思路

题目为一般的树的档次遍历
用广搜能够轻松的实现该题
具体思路与该题相似 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)。

// 有应用空间存储哈希映射吗，为什么官解的复杂度剖析有提这个

退出移动版