力扣面试150题--完全二叉树的节点个数

Day 51

题目描述

思路

根据完全二叉树的规律，完全二叉树的高度可以直接通过不断地访问左子树就可以获取，判断左右子树的高度:
1. 如果相等说明左子树是满二叉树, 然后进一步判断右子树的节点数(最后一层最后出现的节点必然在右子树中）
2. 如果不等说明右子树是深度小于左子树的满二叉树, 然后进一步判断左子树的节点数(最后一层最后出现的节点必然在左子树中

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public int countNodes(TreeNode root) {if(root==null){return 0;}int left=findhigh(root.left);int right=findhigh(root.right);if(left==right){return (int)Math.pow(2,left)+countNodes(root.right);//左子树是满二叉树，右子树是完全二叉树}else{return (int)Math.pow(2,right)+countNodes(root.left);//右子树是少一层的满二叉树，左子树是完全二叉树}}public int findhigh(TreeNode root){int high=0;while(root!=null){root=root.left;high++;}return high;}
}