100. 相同的树 Same Tree 🌟

101. 对称二叉树 Symmetric Tree 🌟

102. 二叉树的层序遍历 Binary Tree Level-order Traversal 🌟🌟

🌟 每日一练刷题专栏 🌟

Golang每日一练专栏

Python每日一练专栏

C/C++每日一练专栏

Java每日一练专栏

二叉树专题（3）

100. 相同的树 Same Tree

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

示例 1：

输入：p = [1,2,3], q = [1,2,3]
输出：true

示例 2：

输入：p = [1,2], q = [1,null,2]
输出：false

示例 3：

输入：p = [1,2,1], q = [1,1,2]
输出：false

提示：

两棵树上的节点数目都在范围 [0, 100] 内
-10^4 <= Node.val <= 10^4

代码1：递归

package mainimport ("fmt""strconv"
)const null = -1 << 31type TreeNode struct {Val   intLeft  *TreeNodeRight *TreeNode
}func isSameTree(p *TreeNode, q *TreeNode) bool {if p == nil && q == nil {return true} else if p != nil && q != nil {if p.Val != q.Val {return false}return isSameTree(p.Left, q.Left) && isSameTree(p.Right, q.Right)} else {return false}
}func buildTree(nums []int) *TreeNode {if len(nums) == 0 {return nil}root := &TreeNode{Val: nums[0]}Queue := []*TreeNode{root}idx := 1for idx < len(nums) {node := Queue[0]Queue = Queue[1:]if nums[idx] != null {node.Left = &TreeNode{Val: nums[idx]}Queue = append(Queue, node.Left)}idx++if idx < len(nums) && nums[idx] != null {node.Right = &TreeNode{Val: nums[idx]}Queue = append(Queue, node.Right)}idx++}return root
}func levelOrder(root *TreeNode) string {if root == nil {return "[]"}arr := []int{}que := []*TreeNode{root}for len(que) > 0 {levelSize := len(que)for i := 0; i < levelSize; i++ {node := que[0]que = que[1:]if node == nil {arr = append(arr, null)continue}arr = append(arr, node.Val)que = append(que, node.Left, node.Right)}}size := len(arr)for size > 0 && arr[size-1] == null {arr = arr[:size-1]size = len(arr)}result := "["for i, n := range arr {if n == null {result += "null"} else {result += strconv.FormatInt(int64(n), 10)}if i < size-1 {result += ","} else {result += "]"}}return result
}func main() {nums1 := []int{1, 2, 3}nums2 := []int{1, 2, 3}root1 := buildTree(nums1)root2 := buildTree(nums2)fmt.Println(levelOrder(root1))fmt.Println(levelOrder(root2))fmt.Println(isSameTree(root1, root2))nums1 = []int{1, 2}nums2 = []int{1, null, 2}root1 = buildTree(nums1)root2 = buildTree(nums2)fmt.Println(levelOrder(root1))fmt.Println(levelOrder(root2))fmt.Println(isSameTree(root1, root2))
}

输出：

[1,2,3]
[1,2,3]
true

[1,2]
[1,null,2]
false

代码2：非递归

1. 定义一个栈，将 p 和 q 按顺序入栈。

2. 当栈不为空时，弹出栈顶元素，判断它们的值是否相等。如果不相等，返回 false。

3. 如果它们的值相等，继续判断它们的左右子树是否相等。如果 p 和 q 的左子树都不为空，则将它们的左子树按顺序入栈。如果 p 和 q 的右子树都不为空，则将它们的右子树按顺序入栈。

4. 如果栈为空，则说明 p 和 q 的所有节点都已经比较完毕，返回 true。

package mainimport ("fmt""strconv"
)const null = -1 << 31type TreeNode struct {Val   intLeft  *TreeNodeRight *TreeNode
}func isSameTree(p *TreeNode, q *TreeNode) bool {stack := []*TreeNode{p, q}for len(stack) > 0 {p, q := stack[len(stack)-2], stack[len(stack)-1]stack = stack[:len(stack)-2]if p == nil && q == nil {continue} else if p == nil || q == nil {return false} else if p.Val != q.Val {return false} else {stack = append(stack, p.Left, q.Left, p.Right, q.Right)}}return true
}func buildTree(nums []int) *TreeNode {if len(nums) == 0 {return nil}root := &TreeNode{Val: nums[0]}Queue := []*TreeNode{root}idx := 1for idx < len(nums) {node := Queue[0]Queue = Queue[1:]if nums[idx] != null {node.Left = &TreeNode{Val: nums[idx]}Queue = append(Queue, node.Left)}idx++if idx < len(nums) && nums[idx] != null {node.Right = &TreeNode{Val: nums[idx]}Queue = append(Queue, node.Right)}idx++}return root
}func levelOrder(root *TreeNode) string {if root == nil {return "[]"}arr := []int{}que := []*TreeNode{root}for len(que) > 0 {levelSize := len(que)for i := 0; i < levelSize; i++ {node := que[0]que = que[1:]if node == nil {arr = append(arr, null)continue}arr = append(arr, node.Val)que = append(que, node.Left, node.Right)}}size := len(arr)for size > 0 && arr[size-1] == null {arr = arr[:size-1]size = len(arr)}result := "["for i, n := range arr {if n == null {result += "null"} else {result += strconv.FormatInt(int64(n), 10)}if i < size-1 {result += ","} else {result += "]"}}return result
}func main() {nums1 := []int{1, 2, 3}nums2 := []int{1, 2, 3}root1 := buildTree(nums1)root2 := buildTree(nums2)fmt.Println(levelOrder(root1))fmt.Println(levelOrder(root2))fmt.Println(isSameTree(root1, root2))nums1 = []int{1, 2}nums2 = []int{1, null, 2}root1 = buildTree(nums1)root2 = buildTree(nums2)fmt.Println(levelOrder(root1))fmt.Println(levelOrder(root2))fmt.Println(isSameTree(root1, root2))
}

101. 对称二叉树 Symmetric Tree

给你一个二叉树的根节点 root ，检查它是否轴对称。

示例 1：

输入：root = [1,2,2,3,4,4,3]
输出：true

示例 2：

输入：root = [1,2,2,null,3,null,3]
输出：false

提示：

树中节点数目在范围 [1, 1000] 内
-100 <= Node.val <= 100

进阶：你可以运用递归和迭代两种方法解决这个问题吗？

代码1：递归

package mainimport ("fmt""strconv"
)const null = -1 << 31type TreeNode struct {Val   intLeft  *TreeNodeRight *TreeNode
}func isSymmetric(root *TreeNode) bool {if root == nil {return true}return helper(root.Left, root.Right)
}func helper(left, right *TreeNode) bool {if left == nil && right == nil {return true} else if left == nil || right == nil {return false} else if left.Val != right.Val {return false} else {return helper(left.Left, right.Right) && helper(left.Right, right.Left)}
}func buildTree(nums []int) *TreeNode {if len(nums) == 0 {return nil}root := &TreeNode{Val: nums[0]}Queue := []*TreeNode{root}idx := 1for idx < len(nums) {node := Queue[0]Queue = Queue[1:]if nums[idx] != null {node.Left = &TreeNode{Val: nums[idx]}Queue = append(Queue, node.Left)}idx++if idx < len(nums) && nums[idx] != null {node.Right = &TreeNode{Val: nums[idx]}Queue = append(Queue, node.Right)}idx++}return root
}func levelOrder(root *TreeNode) string {if root == nil {return "[]"}arr := []int{}que := []*TreeNode{root}for len(que) > 0 {levelSize := len(que)for i := 0; i < levelSize; i++ {node := que[0]que = que[1:]if node == nil {arr = append(arr, null)continue}arr = append(arr, node.Val)que = append(que, node.Left, node.Right)}}size := len(arr)for size > 0 && arr[size-1] == null {arr = arr[:size-1]size = len(arr)}result := "["for i, n := range arr {if n == null {result += "null"} else {result += strconv.FormatInt(int64(n), 10)}if i < size-1 {result += ","} else {result += "]"}}return result
}func main() {nums := []int{1, 2, 2, 3, 4, 4, 3}root := buildTree(nums)fmt.Println(levelOrder(root))fmt.Println(isSymmetric(root))nums = []int{1, 2, 2, null, 3, null, 3}root = buildTree(nums)fmt.Println(levelOrder(root))fmt.Println(isSymmetric(root))nums = []int{1, 2, 2, null, 3, 3}root = buildTree(nums)fmt.Println(levelOrder(root))fmt.Println(isSymmetric(root))
}

输出：

[1,2,2,3,4,4,3]
true

[1,2,2,null,3,null,3]
false

[1,2,2,null,3,3]
true

代码2：非递归

使用队列进行迭代，每次将左右子树的节点按照对称的方式入队，然后依次出队进行比较，如果不相等则返回 false，如果相等则继续迭代。

package mainimport ("fmt""strconv"
)const null = -1 << 31type TreeNode struct {Val   intLeft  *TreeNodeRight *TreeNode
}func isSymmetric(root *TreeNode) bool {if root == nil {return true}queue := []*TreeNode{root.Left, root.Right}for len(queue) > 0 {left, right := queue[0], queue[1]queue = queue[2:]if left == nil && right == nil {continue} else if left == nil || right == nil {return false} else if left.Val != right.Val {return false} else {queue = append(queue, left.Left, right.Right, left.Right, right.Left)}}return true
}func buildTree(nums []int) *TreeNode {if len(nums) == 0 {return nil}root := &TreeNode{Val: nums[0]}Queue := []*TreeNode{root}idx := 1for idx < len(nums) {node := Queue[0]Queue = Queue[1:]if nums[idx] != null {node.Left = &TreeNode{Val: nums[idx]}Queue = append(Queue, node.Left)}idx++if idx < len(nums) && nums[idx] != null {node.Right = &TreeNode{Val: nums[idx]}Queue = append(Queue, node.Right)}idx++}return root
}func levelOrder(root *TreeNode) string {if root == nil {return "[]"}arr := []int{}que := []*TreeNode{root}for len(que) > 0 {levelSize := len(que)for i := 0; i < levelSize; i++ {node := que[0]que = que[1:]if node == nil {arr = append(arr, null)continue}arr = append(arr, node.Val)que = append(que, node.Left, node.Right)}}size := len(arr)for size > 0 && arr[size-1] == null {arr = arr[:size-1]size = len(arr)}result := "["for i, n := range arr {if n == null {result += "null"} else {result += strconv.FormatInt(int64(n), 10)}if i < size-1 {result += ","} else {result += "]"}}return result
}func main() {nums := []int{1, 2, 2, 3, 4, 4, 3}root := buildTree(nums)fmt.Println(levelOrder(root))fmt.Println(isSymmetric(root))nums = []int{1, 2, 2, null, 3, null, 3}root = buildTree(nums)fmt.Println(levelOrder(root))fmt.Println(isSymmetric(root))nums = []int{1, 2, 2, null, 3, 3}root = buildTree(nums)fmt.Println(levelOrder(root))fmt.Println(isSymmetric(root))
}

代码3：中序对称

先中序遍历二叉树，然后判断中序遍历结果是否是对称序列。

package mainimport ("fmt""strconv"
)const null = -1 << 31type TreeNode struct {Val   intLeft  *TreeNodeRight *TreeNode
}func isSymmetric(root *TreeNode) bool {if root == nil {return true}vals := make([]int, 0)inorder(root, &vals)n := len(vals)for i := 0; i < n/2; i++ {if vals[i] != vals[n-i-1] {return false}}return true
}func inorder(root *TreeNode, vals *[]int) {if root == nil {*vals = append(*vals, -1)return}inorder(root.Left, vals)*vals = append(*vals, root.Val)inorder(root.Right, vals)
}func buildTree(nums []int) *TreeNode {if len(nums) == 0 {return nil}root := &TreeNode{Val: nums[0]}Queue := []*TreeNode{root}idx := 1for idx < len(nums) {node := Queue[0]Queue = Queue[1:]if nums[idx] != null {node.Left = &TreeNode{Val: nums[idx]}Queue = append(Queue, node.Left)}idx++if idx < len(nums) && nums[idx] != null {node.Right = &TreeNode{Val: nums[idx]}Queue = append(Queue, node.Right)}idx++}return root
}func levelOrder(root *TreeNode) string {if root == nil {return "[]"}arr := []int{}que := []*TreeNode{root}for len(que) > 0 {levelSize := len(que)for i := 0; i < levelSize; i++ {node := que[0]que = que[1:]if node == nil {arr = append(arr, null)continue}arr = append(arr, node.Val)que = append(que, node.Left, node.Right)}}size := len(arr)for size > 0 && arr[size-1] == null {arr = arr[:size-1]size = len(arr)}result := "["for i, n := range arr {if n == null {result += "null"} else {result += strconv.FormatInt(int64(n), 10)}if i < size-1 {result += ","} else {result += "]"}}return result
}func main() {nums := []int{1, 2, 2, 3, 4, 4, 3}root := buildTree(nums)fmt.Println(levelOrder(root))fmt.Println(isSymmetric(root))nums = []int{1, 2, 2, null, 3, null, 3}root = buildTree(nums)fmt.Println(levelOrder(root))fmt.Println(isSymmetric(root))nums = []int{1, 2, 2, null, 3, 3}root = buildTree(nums)fmt.Println(levelOrder(root))fmt.Println(isSymmetric(root))
}

102. 二叉树的层序遍历 Binary Tree Level-order Traversal

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。（即逐层地，从左到右访问所有节点）。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

示例 2：

输入：root = [1]
输出：[[1]]

示例 3：

输入：root = []
输出：[]

提示：

树中节点数目在范围 [0, 2000] 内
-1000 <= Node.val <= 1000

代码1： 队列实现广度优先搜索 BFS

从根节点开始，将其加入队列中，然后不断从队列中取出节点，将其左右子节点加入队列中，直到队列为空，遍历完成。在遍历每一层时，将该层的节点值加入结果数组的末尾。

package mainimport ("fmt"
)const null = -1 << 31type TreeNode struct {Val   intLeft  *TreeNodeRight *TreeNode
}func levelOrder(root *TreeNode) [][]int {if root == nil {return [][]int{}}var res [][]intqueue := []*TreeNode{root}for len(queue) > 0 {size := len(queue)level := []int{}for i := 0; i < size; i++ {node := queue[0]queue = queue[1:]level = append(level, node.Val)if node.Left != nil {queue = append(queue, node.Left)}if node.Right != nil {queue = append(queue, node.Right)}}res = append(res, level)}return res
}func buildTree(nums []int) *TreeNode {if len(nums) == 0 {return nil}root := &TreeNode{Val: nums[0]}Queue := []*TreeNode{root}idx := 1for idx < len(nums) {node := Queue[0]Queue = Queue[1:]if nums[idx] != null {node.Left = &TreeNode{Val: nums[idx]}Queue = append(Queue, node.Left)}idx++if idx < len(nums) && nums[idx] != null {node.Right = &TreeNode{Val: nums[idx]}Queue = append(Queue, node.Right)}idx++}return root
}func main() {nums := []int{3, 9, 20, null, null, 15, 7}root := buildTree(nums)fmt.Println(levelOrder(root))
}

输出：

[[3] [9 20] [15 7]]

代码2： 递归实现深度优先搜索 DFS

对于每一层，先遍历左子树，然后遍历右子树，直到遍历完所有层。在遍历每一层时，将该层的节点值加入结果数组的末尾。

package mainimport ("fmt"
)const null = -1 << 31type TreeNode struct {Val   intLeft  *TreeNodeRight *TreeNode
}func levelOrder(root *TreeNode) [][]int {var res [][]intdfs(root, 0, &res)return res
}func dfs(node *TreeNode, level int, res *[][]int) {if node == nil {return}if level == len(*res) {*res = append(*res, []int{})}(*res)[level] = append((*res)[level], node.Val)dfs(node.Left, level+1, res)dfs(node.Right, level+1, res)
}func buildTree(nums []int) *TreeNode {if len(nums) == 0 {return nil}root := &TreeNode{Val: nums[0]}Queue := []*TreeNode{root}idx := 1for idx < len(nums) {node := Queue[0]Queue = Queue[1:]if nums[idx] != null {node.Left = &TreeNode{Val: nums[idx]}Queue = append(Queue, node.Left)}idx++if idx < len(nums) && nums[idx] != null {node.Right = &TreeNode{Val: nums[idx]}Queue = append(Queue, node.Right)}idx++}return root
}func main() {nums := []int{3, 9, 20, null, null, 15, 7}root := buildTree(nums)fmt.Println(levelOrder(root))
}