如何建设旅游网站,做网站去哪里找广告主,wordpress添加会员等级标识,网页设计代码模板适应手机界面二叉树我最近刷的特别多#xff0c;差不多快刷完了#xff0c;但是有一种题型差点给我忽略了#xff0c;那就是完全二叉树#xff0c;这也是一个很重要的题型#xff0c;今天刚好有一道题目可以来复习一下完全二叉树的特性 题目链接如下#xff1a;https://leetcode.cn/… 二叉树我最近刷的特别多差不多快刷完了但是有一种题型差点给我忽略了那就是完全二叉树这也是一个很重要的题型今天刚好有一道题目可以来复习一下完全二叉树的特性 题目链接如下https://leetcode.cn/problems/count-complete-tree-nodes/?envTypestudy-plan-v2envIdtop-interview-150 做这道题首先有一点要知道的就是完全二叉树是怎么样子的下面说一下完全二叉树的概念 完全二叉树只有最底层的节点未被填满且最底层节点尽量靠左填充 ok 现在已经了解了基础概念了我们再来看这道题目 这道题目的目的是让我们遍历这棵树并算有几个节点 说实话这道题很简单用暴力的做法就是遍历一整棵树代码如下 递归法
//方法一递归
func Solution222(root *TreeNode) int {if root nil {return 0}left : Solution222(root.Left)right : Solution222(root.Right)return left right 1
}迭代法
//方法二迭代
func Solution222v2(root *TreeNode) int {if root nil{return 0}queue : []*TreeNode{root}count : 0for len(queue) 0{node : queue[0]queue queue[1:]countif node.Left ! nil{queue append(queue, node.Left)}if node.Right ! nil{queue append(queue, node.Right)}}return count
}这两个方法是遍历树的最基本的方法之一 但是 这不是这道题的本意这道题目是想要我们理由完全二叉树这个特性解题 那我们需要好好思考一下完全二叉树有什么特点 除了最后的叶子节点其他层级节点都是满的 当 左子树的深度 和 右子树的深度 一致的时候说明 左子树是满的二叉树 可以通过 2的h次方求的左子树的节点个数 当 右子树的深度 不如 左子树的深度 的时候说明 左子树不是一个满的二叉树但是右子树单独看是一个满的二叉树所以可以通过 2的h次方求右子树的节点个数 ok知道这些特点我们是不是可以利用一个逻辑来减少遍历 当 左子树深度 等于 右子树的时候就可以通过深度来计算左子树的节点然后只遍历右子树当 左子树深度 等于 右子树的时候就可以通过深度来计算右子树的节点然后只遍历左子树 这样我们本来需要遍历全部二叉树节点的现在只需要遍历一半思路瞬间打开代码如下
//方法三二分查找
func Solution222v3(root *TreeNode) int {if root nil{return 0}//检索左子树深度left : root.Leftldepth : 0for left ! nil{left left.Leftldepth}//检索右子树深度right : root.Rightrdepth : 0for right ! nil{right right.Leftrdepth}//左右子树深度判断if ldepth rdepth{return (1ldepth) Solution222v3(root.Right)}else{return (1rdepth) Solution222v3(root.Left)}
} ok这里这道题目就结束了感谢大家观看
