@(labuladong的算法小抄)[完全二叉樹]

leetcode 222. 完全二叉樹的節點個數

題目描述

解題思路

參考：labuladong的算法小抄P243

如果是普通二叉樹，可以直接用遞歸做，但這題是完全二叉樹，是以可以利用特性做。

class Solution {
    public int countNodes(TreeNode root) {
        if (root == null) return 0;
        TreeNode l = root, r = root;
        /* 記錄左右子樹的高度 */
        int hl = 0, hr = 0;
        while (l != null) {
            l = l.left;
            hl++;
        }
        while (r != null) {
            r = r.right;
            hr++;
        }
        /* 如果左右子樹高度相同，說明是一棵滿二叉樹 */
        if (hl == hr) {
            return (int)Math.pow(2, hl) - 1;
        }
        /* 如果左右子樹高度不同，則按照普通二叉樹的邏輯計算 */
        return 1 + countNodes(root.left) + countNodes(root.right);
    }
}