书店网站html模板,建立网站得多少钱,网站开发主要语言,宝安做网站多少钱222. 完全二叉树的节点个数
题目描述#xff1a; 给你一棵 完全二叉树的根节点 root #xff0c;求出该树的节点个数。
完全二叉树的定义如下#xff1a;在完全二叉树中#xff0c;除了最底层节点可能没填满外#xff0c;其余每层节点数都达到最大值#xff0c;并且最下…222. 完全二叉树的节点个数
题目描述 给你一棵 完全二叉树的根节点 root 求出该树的节点个数。
完全二叉树的定义如下在完全二叉树中除了最底层节点可能没填满外其余每层节点数都达到最大值并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层则该层包含 1~ 2h 个节点。
如果存在则返回 true不存在返回 false。
考察重点完全二叉树定义
方法概括递归遍历左右子树的深度左右子树深度一致说明以当前节点为根的左子树一定是完全二叉树左右子树深度不一致说明以当前节点为根的右子树一定是完全二叉树
func getDepth(root *d.TreeNode) int { //计算当前结点的最大深度。由于是完全二叉树所以最大深度等于最大左子树深度res : 0for root ! nil {resroot root.Left}return res
}func CountNodes(root *d.TreeNode) int {if root nil {return 0}if root.Left nil root.Right nil {return 1}left : getDepth(root.Left) //得到左右子树深度right : getDepth(root.Right)/**左右子树深度一致说明以root1为根的左子树一定是完全二叉树右子树不一定。所以总结点数完全二叉左子树 根节点 右子树1 12 3 2 32 2 3 2 2 3 3左右子树深度不一致说明以root1为根的右子树一定是完全二叉树左子树一定不是。所以总结点数完全二叉右子树 根节点 左子树12 32 2 3 32 2*/if left right { //如果深度一致向右子树继续遍历同时加上完全二叉的左子树与根节点return CountNodes(root.Right) (1left - 1) 1} else { //如果深度不一致向左子树继续遍历同时加上完全二叉的右子树与根节点return CountNodes(root.Left) (1right - 1) 1}
}
