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