题解 | #二叉树的最大深度#

package main

import "fmt"

// 二叉树节点
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// 递归版本
func maxDepth1(root *TreeNode) int {
	// write code here
	if root == nil {
		return 0
	}
	leftDepth := maxDepth1(root.Left)
	rightDepth := maxDepth1(root.Right)
	return max(leftDepth, rightDepth) + 1
}

// 非递归版本
func maxDepth2(root *TreeNode) int {
	// write code here
	if root == nil {
		return 0
	}
	stack := []*TreeNode{root}
	depth := 0
	for len(stack) > 0 {
		// 新建一个切片来存储下一层的节点
		var nextLevel []*TreeNode

		for _, node := range stack {
			if node.Left != nil {
				nextLevel = append(nextLevel, node.Left)
			}

			if node.Right != nil {
				nextLevel = append(nextLevel, node.Right)
			}
		}

		// 更新栈为下一层的节点
		stack = nextLevel
		depth++
	}

	return depth
}

func main() {
	// 示例用法
	// 创建一个二叉树:     1
	//                  / \
	//                 2   3
	//                /     \
	//               4       5
	tree := &TreeNode{
		Val: 1,
		Left: &TreeNode{
			Val: 2,
			Left: &TreeNode{
				Val: 4,
			},
		},
		Right: &TreeNode{
			Val: 3,
			Right: &TreeNode{
				Val: 5,
			},
		},
	}
	fmt.Println(maxDepth2(tree))
}

递归法很容易理解。

非递归法，创建一个stack，添加根节点，找寻孩子加入stack，然后对应的dep++，之后把当前的节点出栈，之后一直持续操作，能找到最深一层的dep，返回即可