目录
- 完全二叉树的节点个数
- 平衡二叉树110
- 二叉树的所有路径257
- 左叶子之和404
一、完全二叉树的节点个数
https://leetcode.cn/problems/count-complete-tree-nodes/description/?envType=problem-list-v2&envId=8At1GmaZ
方法一:用普适的递归方法来做,这样会遍历到每一个节点。没有利用完全二叉树的性质。- class Solution {
- public int countNodes(TreeNode root) {
- if(root == null){
- return 0;
- }
- return countNodes(root.left) + countNodes(root.right) + 1;
- }
- }
- //时间复杂度:O(n)
复制代码 方法二:充分利用了“完全二叉树”的结构,避免了重复计算完整子树的节点个数,大大减少了递归次数,因此时间复杂度从 O(n) 降低到了 O((log n)^2),在大数据量时性能优势明显。
- 完全二叉树的特点是:左子树深度等于右子树深度 ⇒ 整个左子树是满二叉树,节点数是 2^depth - 1。
- 利用这一性质,可以直接跳过对整棵子树的递归计算,用位运算直接得出节点数。
[code]class Solution { public int countNodes(TreeNode root) { if(root == null){ return 0; } int left = countLevel(root.left); int right = countLevel(root.right); if(left == right){ return countNodes(root.right) + (1 |