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;}
}
)
