目录
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 main
import (
"fmt"
"strconv"
)
const null = -1 << 31
type TreeNode struct {
Val int
Left *TreeNode
Right *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 := 1
for 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 main
import (
"fmt"
"strconv"
)
const null = -1 << 31
type TreeNode struct {
Val int
Left *TreeNode
Right *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 := 1
for 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 main
import (
"fmt"
"strconv"
)
const null = -1 << 31
type TreeNode struct {
Val int
Left *TreeNode
Right *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 := 1
for 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 main
import (
"fmt"
"strconv"
)
const null = -1 << 31
type TreeNode struct {
Val int
Left *TreeNode
Right *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 := 1
for 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 main
import (
"fmt"
"strconv"
)
const null = -1 << 31
type TreeNode struct {
Val int
Left *TreeNode
Right *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 := 1
for 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 main
import (
"fmt"
)
const null = -1 << 31
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
func levelOrder(root *TreeNode) [][]int {
if root == nil {
return [][]int{}
}
var res [][]int
queue := []*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 := 1
for 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 main
import (
"fmt"
)
const null = -1 << 31
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
func levelOrder(root *TreeNode) [][]int {
var res [][]int
dfs(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 := 1
for 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))
}
🌟 每日一练刷题专栏 🌟
✨ 持续,努力奋斗做强刷题搬运工!
👍 点赞,你的认可是我坚持的动力!
🌟 收藏,你的青睐是我努力的方向!
✎ 评论,你的意见是我进步的财富!
☸ 主页:https://hannyang.blog.csdn.net/
Golang每日一练 专栏 | |
Python每日一练 专栏 | |
C/C++每日一练 专栏 | |
Java每日一练 专栏 |