中文域名和网站的关系,校园网站制作模板,如何自己开发一款游戏,工程建设规范前言
问问自己#xff0c;刷题的效果真的达到了吗#xff1f;
内容
一、翻转二叉树
226.翻转二叉树
给你一棵二叉树的根节点 root #xff0c;翻转这棵二叉树#xff0c;并返回其根节点。
递归
func invertTree(root *TreeNode) *TreeNode {if rootnil{return root}…前言
问问自己刷题的效果真的达到了吗
内容
一、翻转二叉树
226.翻转二叉树
给你一棵二叉树的根节点 root 翻转这棵二叉树并返回其根节点。
递归
func invertTree(root *TreeNode) *TreeNode {if rootnil{return root}root.Left,root.Rightroot.Right,root.LeftinvertTree(root.Left)invertTree(root.Right)return root
}
二、对称二叉树
101.对称二叉树
给你一个二叉树的根节点 root 检查它是否轴对称。
递归
我们可以实现这样一个递归函数通过「同步移动」两个指针的方法来遍历这棵树p 指针和 q 指针一开始都指向这棵树的根随后 p 右移时q 左移p 左移时q 右移。每次检查当前 p 和 q 节点的值是否相等如果相等再判断左右子树是否对称。
func isSymmetric(root *TreeNode) bool {return dfs(root.Left,root.Right)}func dfs(left *TreeNode,right *TreeNode) bool{if leftnilrightnil{return true}if leftnil||rightnil{return false}if left.Val!right.Val{return false}return dfs(left.Left,right.Right)dfs(left.Right,right.Left)
}
迭代
把递归程序改写成迭代程序
func isSymmetric(root *TreeNode)bool{u,v:root,rootqueue:[]*TreeNode{}queueappend(queue,u)queueappend(queue,v)for len(queue)0{u,v queue[0],queue[1]queuequeue[2:]if unilvnil{//要先判断continue}if unil||vnil{return false}if u.Val!v.Val{return false}queueappend(queue,u.Left)queueappend(queue,v.Right)queueappend(queue,u.Right)queueappend(queue,v.Left)}return true
}
三、完全二叉树的节点个数
222.完全二叉树的节点个数
给你一棵 完全二叉树 的根节点 root 求出该树的节点个数。
完全二叉树 的定义如下在完全二叉树中除了最底层节点可能没填满外其余每层节点数都达到最大值并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层则该层包含 1~ 2h 个节点。
广度优先搜素
func countNodes(root *TreeNode) int {var count intif rootnil{//没有这个会报错 昨天遇到过return 0}level:[]*TreeNode{root}for len(level)0{temp:levellevelnilfor _,node:range temp{countif node.Left!nil{levelappend(level,node.Left)}if node.Right!nil{levelappend(level,node.Right)}}}return count
}
最后
令人心动的offer啊能拿到吗
