二叉树.md

二叉树

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

遍历

前序遍历：先访问根节点，再前序遍历左子树，再前序遍历右子树；

中序遍历：先中序遍历左子树，再访问根节点，再中序遍历右子树；

后序遍历：先后续遍历左子树，再后续遍历右子树，再访问根节点

• 以根访问的顺序决定是什么遍历；
• 左子树都是优先右子树

递归序

func trversal(root *TreeNode) { 
    if root == nil { 
        return
    }

    fmt.Println(root.Val) // 先序遍历
    trversal(root.Left)
    // fmt.Println(root.Val) // 中序遍历
    trversal(root.Right)
    // fmt.Println(root.Val) // 后序遍历
}

前序遍历(非递归)

func preOrderTraversal(root *TreeNode) []int {
    if root == nil {
        return nil
    }

    result := make([]int, 0)
    stack := make([]*TreeNode, 0)

    for root != nil || len(stack) != 0 {
        for root != nil { 
            // 前序遍历，所以先保存结果
            result = append(result, root.Val)
            stack = append(stack, root)
            root = root.Left
        }
        
        // pop
        node := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        root = node.Right
    }

    return result
}

中序遍历(非递归)

// 通过 stack 保存已访问的元素，用于原路放回
func inOrderTraversal(root *TreeNode) []int {
    result := make([]int, 0)
    if root == nil {
        return nil
    }

    stack := make([]*TreeNode, 0)
    for root != nil || len(stack) > 0 {
        for root != nil {
            stack = append(stack, root)
            root = root.Left
        }

        // 弹出
        node := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        // 中序遍历，中间处理
        result = append(result, node.Val)
        root = node.Right
    }
}

例子：合法二叉搜索树

面试题 04.05. 合法二叉搜索树

// 中序遍历（递归）解法
func isValidBST(root *TreeNode) bool {

    lo := math.MinInt64
    hi := math.MaxInt64
    return inOrderTraversal(root, lo, hi)
    
}

func inOrderTraversal(root *TreeNode, lo int, hi int) bool {
    
    if root == nil {
        return true
    }

    /* 
    满足三个条件：
        1. 左子树是二叉搜索树；
        2. 右子树是二叉搜索树；
        3. 左子树的最大值小于 root 的值小于右子树的最小值；
    */
    if root.Val <= lo || root.Val >= hi {
        return false
    }
    
    return inOrderTraversal(root.Left, lo, root.Val) && inOrderTraversal(root.Right, root.Val, hi)
}

// 中序遍历（非递归）解法
func isValidBST(root *TreeNode) bool {
    stack := []*TreeNode{}
    inorder := math.MinInt64

    for len(stack) > 0 || root != nil {
        for root != nil {
            stack = append(stack, root)
            root = root.Left
        }

        root = stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        if root.Val <= inorder {
            return false
        }
        inorder = root.Val
        root = root.Right
    }

    return true
}

701. 二叉搜索树中的插入操作

func insertIntoBST(root *TreeNode, val int) *TreeNode {
    if root == nil {
        root = &TreeNode{Val: val}
        return root
    }
    if root.Val > val {
        root.Left = insertIntoBST(root.Left, val)
    } else {
        root.Right = insertIntoBST(root.Right, val)
    }
    return root
}

后序遍历(非递归)

func postOrderTraversal(root *TreeNode) []int {
    if root == nil {
        return nil
    }

    result := make([]int, 0)
    stack := make([]*TreeNode, 0)
    var lastVisit *TreeNode
    for root != nil || len(stack) > 0 {
        for root != nil {
            stack = append(stack, root)
            root = root.Left
        }

        // 这里先看看，不弹出
        node := stack[len(stack)-1]
        if node.Right == nil || node.Right == lastVisit {
            // 弹出
            stack = stack[:len(stack)-1]
            result = append(result, node.Val)

            // 标记当前这个节点已经弹出过
            lastVisit = node
        } else {
            root = root.Right
        }
    }
}

前序遍历（DFS）

二叉树 DFS

DFS 深度搜索 -- 从上到下

func preOrderTraversal(root *TreeNode) []int {
    result := make([]int, 0)
    dfs(root, &result)
    return result
}

// 深度遍历，结果指针作为参数传入到函数内部
func dfs(root *TreeNode, result *[]int) {
    if root == nil {
        return
    }

    *result = append(*result, root.Val)
    dfs(root.Left, result)
    dfs(root.Right, result)
}

DFS 深度搜索 -- 从下向上（分治法）

func preOrderTraversal(root *TreeNode) []int {
    result := divideAndConquer(root)
    return result
}

func divideAndConquer(root *TreeNode) []int {
    result := make([]int, 0)
    if root == nil {
        return result
    }

    // Divide
    left := divideAndConquer(root.Left)
    right := divideAndConquer(root.Right)
    // Conquer
    result = append(result, root.Val)
    result = append(result, left...)
    result = append(result, right...)
    return result
}

DFS 深度搜索（从上到下） 和分治法区别：前者一般将最终结果通过指针参数传入，后者一般递归返回结果最后合并.

二叉树最大深度

104. 二叉树的最大深度

func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    
    // divide
    left := maxDepth(root.Left)
    right := maxDepth(root.Right)
    
    // Conquer
    if left > right {
        return left + 1
    }
    return right + 1
}

平衡二叉树

110. 平衡二叉树

思路：分治法，左边平衡 && 右边平衡 && 左右两边高度 <= 1， 因为需要返回是否平衡及高度，要么返回两个数据，要么合并两个数据， 所以用-1 表示不平衡，>0 表示树高度（二义性：一个变量有两种含义）。

func isBalanced(root *TreeNode) bool {
    if maxDepth(root) == -1 {
        return false
    }
    return true
}

func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    
    // divide
    left := maxDepth(root.Left)
    right := maxDepth(root.Right)
    
    // Conquer
    if left == -1 || right == -1 || left - right > 1 || right - left > 1 {
        return -1
    }

    if left > right {
        return left + 1
    }
    return right + 1
}

二叉树中的最大路径和

124. 二叉树中的最大路径和

思路：分治法，分为三种情况：左子树最大路径和最大，右子树最大路径和最大，左右子树最大加根节点最大，需要保存两个变量：一个保存子树最大路径和，一个保存左右加根节点和，然后比较这个两个变量选择最大值即可.

type ResultType struct {
    SinglePath int // 保存单边最大值
    MaxPath    int // 保存最大值（单边或者两个单边+根的值）
}

func maxPathSum(root *TreeNode) int {
    result := helper(root)
    return result.MaxPath
}

func helper(root *TreeNode) ResultType {
    if root == nil {
        return ResultType{
            SinglePath: 0,
            MaxPath: -(1 << 31)
        }
    }

    // Divide
    left := helper(root.left)
    right := helper(root.Right)

    // Conquer
    result := ResultType{}

    // 求单边最大值
    if left.SinglePath > right.SinglePath {
        result.SinglePath = max(left.SinglePath + root.Val, 0)
    } else {
        result.SinglePath = max(right.SinglePath + root.Val, 0)
    }

    // 求两边加根最大值
    maxPath := max(left.MaxPath, right.MaxPath)
    result.MaxPath = max(maxPath, left.SinglePath + right.SinglePath + root.Val)
    return result
}

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}

最低公共祖先

236. 二叉树的最近公共祖先

思路：分治法，有左子树的公共祖先或者有右子树的公共祖先，就返回子树的祖先，否则返回根节点

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    if root == nil {
        return root
    }

    if root == p || root == q {
        return root
    }

    // divide 
    l := lowestCommonAncestor(root.Left, p, q)
    r := lowestCommonAncestor(root.Right, p, q)

    // conquer
    if l != nil && r != nil {
        return root
    }
    if l != nil {
        return l
    }
    if r != nil {
        return r
    }
    return nil
}

二叉树 BFS

二叉树层序遍历

102. 二叉树的层序遍历

func levelOrder(root *TreeNode) [][]int {
    result := make([][]int, 0)
    if root == nil {
        return result
    }
    queue := make([]*TreeNode, 0)
    queue = append(queue, root)
    m := map[*TreeNode]int{root: 0}
    curLayer := 0
    layerVals := make([]int, 0)
    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]

        if curLayer != m[node] {
            curLayer++
            result = append(result, layerVals)
            layerVals = make([]int, 0)
        }
        
        if node.Left != nil {
            queue = append(queue, node.Left)
            m[node.Left] = curLayer + 1
        }
        if node.Right != nil {
            queue = append(queue, node.Right)
            m[node.Right] = curLayer + 1
        }
        
        layerVals = append(layerVals, node.Val)
    }
    result = append(result, layerVals)

    return result
}

func levelOrder(root *TreeNode) [][]int {
    result := make([][]int, 0)
    if root == nil {
        return result
    }

    queue := make([]*TreeNode, 0)
    queue = append(queue, root)
    for len(queue) > 0 {
        layerVals := make([]int, 0)
        l := len(queue)
        for i := 0; i < 1; i++ {
            node := queue[0]
            queue = queue[1:]
            layerVals = append(layerVals, node.Val)
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
        result = append(result, layerVals)
    } 
    return result
}

107. 二叉树的层序遍历 II

func levelOrderBottom(root *TreeNode) [][]int {
    result := make([][]int, 0)
    if root == nil {
        return result
    }
    queue := make([]*TreeNode, 0)
    queue = append(queue, root)
    m := map[*TreeNode]int{root: 0}
    curLayer := 0
    layerVals := make([]int, 0)
    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]

        if curLayer != m[node] {
            curLayer++
            result = append(result, layerVals)
            layerVals = make([]int, 0)
        }
        
        if node.Left != nil {
            queue = append(queue, node.Left)
            m[node.Left] = curLayer + 1
        }
        if node.Right != nil {
            queue = append(queue, node.Right)
            m[node.Right] = curLayer + 1
        }
        
        layerVals = append(layerVals, node.Val)
    }
    result = append(result, layerVals)

    reverse(result)

    return result
}

func reverse(nums [][]int) {
    for i, j := 0, len(nums)-1; i < j; i, j = i+1, j-1 {
        nums[i], nums[j] = nums[j], nums[i]
    }
}

103. 二叉树的锯齿形层序遍历

func zigzagLevelOrder(root *TreeNode) [][]int {
    result := make([][]int, 0)
    if root == nil {
        return result
    }
    queue := make([]*TreeNode, 0)
    queue = append(queue, root)
    m := map[*TreeNode]int{root: 0}
    curLayer := 0
    layerVals := make([]int, 0)
    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]

        if curLayer != m[node] {
            curLayer++
            if curLayer % 2 == 0 {
                reverse(layerVals)
                fmt.Println(layerVals)
            }
            result = append(result, layerVals)
            layerVals = make([]int, 0)
        }
        
        if node.Left != nil {
            queue = append(queue, node.Left)
            m[node.Left] = curLayer + 1
        }
        if node.Right != nil {
            queue = append(queue, node.Right)
            m[node.Right] = curLayer + 1
        }
        
        layerVals = append(layerVals, node.Val)
    }
    if curLayer % 2 == 1 {
        reverse(layerVals)
    }
    result = append(result, layerVals)

    return result
}

func reverse(nums []int) {
    for i, j := 0, len(nums)-1; i < j; i, j = i+1, j-1 {
        nums[i], nums[j] = nums[j], nums[i]
    }
}

func zigzagLevelOrder(root *TreeNode) [][]int {
    result := [][]int
    if root == nil {
        return result
    }

    queue := make([]*TreeNode, 0)
    queue = append(queue, root)
    toggle := false

    for len(queue) > 0 {
        layerVals := make([]int, 0)
        l := len(queue)
        for i := 0; i < l; i++ {
            node := queue[0]
            queue = queue[1:]

            layerVals = append(layerVals, node.Val)
            
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }

        }
        if toggle {
            reverse(layerVals)
        }
        result = append(result, layerVals)
        toggle = !toggle
    }
    return result
}

func reverse(nums []int) {
    for i := 0; i < len(nums) / 2; i++ {
        nums[i], nums[j] = nums[j], nums[i]
    }
}