Leetcode 完全二叉树的节点个数

不讲武德的解法

java 实现

class Solution {public int countNodes(TreeNode root) {if(root == null) return 0;return countNodes(root.left) + countNodes(root.right) + 1;}
}

根据完全二叉树和满二叉树的性质做

class Solution {public int countNodes(TreeNode root) {if (root == null) {return 0;}int leftDepth = getDepth(root.left);int rightDepth = getDepth(root.right);if (leftDepth == rightDepth) {// 左子树是满二叉树，节点数为 2^leftDepth - 1，加上根节点和右子树return (1 << leftDepth) + countNodes(root.right);} else {// 右子树是满二叉树，节点数为 2^rightDepth - 1，加上根节点和左子树return (1 << rightDepth) + countNodes(root.left);}}private int getDepth(TreeNode node) {int depth = 0;while (node != null) {depth++;node = node.left; // 完全二叉树的最左路径}return depth;}
}