网站备案查询 美橙网,网站建设建立好如何盈利,如果做公司网站,网站建设高效解决之道1. 完全二叉树的的节点个数
222. 完全二叉树的节点个数https://leetcode.cn/problems/count-complete-tree-nodes/
给你一棵 完全二叉树 的根节点 root #xff0c;求出该树的节点个数。
完全二叉树 的定义如下#xff1a;在完全二叉树中#xff0c;除了最底层节点可能没…1. 完全二叉树的的节点个数
222. 完全二叉树的节点个数https://leetcode.cn/problems/count-complete-tree-nodes/
给你一棵 完全二叉树 的根节点 root 求出该树的节点个数。
完全二叉树 的定义如下在完全二叉树中除了最底层节点可能没填满外其余每层节点数都达到最大值并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层则该层包含 1~ 2h 个节点。
解题思路
完全二叉树的特点就是最后一层靠左边的是完全有节点的。
常规思路就是On)进行遍历但是这是一个完全二叉树肯定是可以利用完全二叉树的特性来完成的。
如果这是一颗满二叉树那么节点数目为2的n次方减1如果不是满二叉树那就分别计算左右子树的节点个数。而左右子树的个数又可以根据是不是满二叉树进行计算。这就可以依据递归实现。
终止条件节点为null或左右子树深度相等
返回值是左右子树节点个数相加再加1或者2的n次方-1
代码
class Solution {public int countNodes(TreeNode root) {if (root null)return 0;TreeNode left root;TreeNode right root;int deep 0;while (left ! null right ! null) {left left.left;right right.right;deep;}if (left null right null) {return (int) Math.pow(2, deep) - 1;} else {return countNodes(root.left) countNodes(root.right) 1;}}
}
2.平衡二叉树
110. 平衡二叉树https://leetcode.cn/problems/balanced-binary-tree/
给定一个二叉树判断它是否是高度平衡的二叉树。
本题中一棵高度平衡二叉树定义为一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
示例 1 输入root [3,9,20,null,null,15,7]
输出true
示例 2 输入root [1,2,2,3,3,null,null,4,4]
输出false
示例 3
输入root []
输出true
解题思路
这道题的平衡二叉树只和高度差有关左右子树的高度差不大于1的情况下就为平衡二叉树。
但是返回值不能是true因为涉及到高度的传递。
所以返回值为int类型。由于当子树高度差超过1后无法马上return false。为了防止后续迭代进行额外的操作。使用标志位-1发现-1就说明不会是平衡二叉树了直接返回-1。
终止条件root为null的时候返回0
代码
class Solution {public boolean isBalanced(TreeNode root) {return getHeight(root) ! -1;}public int getHeight(TreeNode root) {if (root null)return 0;int left getHeight(root.left);int right getHeight(root.right);if (left -1 || right -1)return -1;if (Math.abs(left - right) 1)return -1;return Math.max(left, right) 1;}
}
