解题思路
求出左子树 根节点到叶子节点的高度 以及 右子树 根节点到叶子节点的高度 。比较高度 利用公式求解
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val = x; }* }*/
class Solution {//思路: 求出左子树 根节点到叶子节点的高度 以及 右子树 根节点到叶子节点的高度//比较高度 利用公式求解public int countNodes(TreeNode root) {if(root == null) return 0;int left = getHigh(root.left);int right = getHigh(root.right);int leftCount = 0;int rightCount = 0;if(left == right){ //说明左子树是满二叉树 再递归遍历右子树leftCount = (int)Math.pow(2,left) - 1 ;rightCount = countNodes(root.right);}else if(left > right){ //左子树比右子树大1 此时右子树是满二叉树 左子树递归rightCount = (int)Math.pow(2,right) - 1;leftCount = countNodes(root.left);}return leftCount +rightCount + 1;}public int getHigh(TreeNode root){if(root == null) return 0;int high = 0;while(root != null){high += 1;root = root.left;}return high;}
}