二叉树的遍历方式

144. 二叉树的前序遍历【简单】


// https://leetcode.cn/problems/binary-tree-preorder-traversal/solution/dai-ma-sui-xiang-lu-chi-tou-qian-zhong-hou-xu-de-d/
// 前序遍历是根左右，每次先处理的是中间节点，那么先将跟节点放入栈中，然后将右孩子加入栈，再加入左孩子。
//为什么要先加入 右孩子，再加入左孩子呢？ 因为这样出栈的时候才是中左右的顺序。
func preorderTraversal(root *TreeNode) []int {
    ans := make([]int, 0)
    stack := []*TreeNode{root}
    for len(stack) != 0 {
        node := stack[len(stack)-1]
        fmt.Println(node)
        if node == nil {
            stack = stack[:len(stack)-1]
            continue
        }
        ans = append(ans, node.Val)
        stack = stack[:len(stack)-1]      // 栈顶元素出来
        stack = append(stack, node.Right) // 先压栈右节点，再压左节点
        stack = append(stack, node.Left)
    }
    return ans
}

145. 二叉树的后序遍历【简单】

94. 二叉树的中序遍历【简单】

102. 二叉树的层序遍历【中等】


// ============== 解法一： BFS 迭代实现，广度优先遍历 ================
func levelOrder(root *TreeNode) (res [][]int) {
    if root == nil {
        return res
    }
    queue := []*TreeNode{root}
    for len(queue) != 0 {
        var curLevel []int
        size := len(queue)
    
        for i := 0; i < size; i++ {
            node := queue[0]
            curLevel = append(curLevel, node.Val)

            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
            queue = queue[1:]
        }
        res = append(res, curLevel)
    }

    return res
}

二叉树的属性

101. 对称二叉树【简单】

104. 二叉树的最大深度【简单】


//**************** 解法一（递归走起）********************************

func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    left := maxDepth(root.Left)                             // 左子树的最大深度
    right := maxDepth(root.Right)                           // 右子树的最大深度
    return int(math.Max(float64(left), float64(right)) + 1) // 深度加上根节点

}

//**************** 解法二（迭代法走起）********************************

func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    queue := []*TreeNode{root} // 辅助队列,根节点入队
    depth := 0                 // 初始化深度为0

    for len(queue) > 0 { // 当队列不为空时，循环以下操作
        size := len(queue)          //当前队列中元素个数size作为限定:当前层级中节点数量
        for i := 0; i < size; i++ { // 遍历当前层级中的节点
            s := queue[0]      // 获取队首元素
            if s.Left != nil { // 如果左子树不为空，左子树入队
                queue = append(queue, s.Left)
            }
            if s.Right != nil { // 如果右子树不为空，右子树入队
                queue = append(queue, s.Right)
            }
            queue = queue[1:] // 队首元素出队
        }
        depth++ // for循环结束后这一层级节点已经访问结束，深度加+1
    }
    return depth
}

111. 二叉树的最小深度【简单】

// ============== 解法一： BFS 迭代实现，广度优先遍历 ================
// https://www.cnblogs.com/Lusai/p/15709094.html
func minDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    var queue []*TreeNode       // 查找队列
    queue = append(queue, root) // 将起点加入队列
    depth := 1                  // root 本身就是一层，depth初始化为1
    for len(queue) != 0 {
        size := len(queue)
        // 将当前队列中的所有结点向四周扩散
        for i := 0; i < size; i++ {
            cur := queue[0]
            // 判断是否到终点
            if cur.Left == nil && cur.Right == nil {
                return depth
            }
            // 将 cur的相邻节点加入队列
            if cur.Left != nil {
                queue = append(queue, cur.Left)
            }
            if cur.Right != nil {
                queue = append(queue, cur.Right)
            }
            // 去掉当前节点
            queue = queue[1:]
        }
        // 这里增加步数
        depth++
    }
    return depth
}

// ============== 解法二： DFS   ================

func minDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    if root.Left != nil && root.Right == nil {
        return 1 + minDepth(root.Left)
    }
    if root.Right != nil && root.Left == nil {
        return 1 + minDepth(root.Right)
    }
    return 1 + Min(minDepth(root.Left), minDepth(root.Right))
}