每日算法之求完全二叉树的结点个数

参考 LeetCode 222题

题目：求一个完全二叉树的结点总数

leetcode222.png

解析：要解决这道题，必须要清楚完全二叉树的特点

完全二叉树：除了最后一层，所有层的节点数达成最大，与此同时，最后一层的所有结点都在左侧。

满二叉树：所有层的结点数都达到最大

解法一：递归法

1.计算出左子树和右子树的高度h

2.如果左子树和右子树的高度一样，则它是一棵满二叉树，结点个数就是(2^h)-1个

3.如果高度不一样，就要递归分别求出左子树和右子树的结点数。结点总数=左子树+右子树+1(根节点)

public int countNodes(TreeNode root) {
    if(root == null) return 0;

    int height = 1;
    TreeNode left = root.left, right = root.right;
    while(left != null && right != null) {
        height++; 
        left = left.left;
        right = right.right;
    }
    
    return left == right ? (1 << height ) - 1 : 1 + countNodes(root.left) + countNodes(root.right);
} 

解法二：迭代法

1.先计算出树的高度h和计算右子树的高度

2.比较右子树是否和树的高度小1来判断，左子树和右子树是不是有相同的高度

3.如果高度相同，那么树的最后一行的最后一个节点在右子树中，而左子树是高度为h-1的整棵树。所以我们取左子树的2^h-1节点数加上右子树中的递归节点数+1（根节点）

4.如果高度不同，那么最后一行树的最后一个节点在左子树中，而右子树是高度为h-2的整棵树。所以我们取右子树的2^（h-1）-1节点加上左子树中的递归节点数+1（根节点）。

public int countNodes2(TreeNode root) {
        int nodes=0,h=height(root);
        System.out.println("---树的最大高度是----"+h);
        while(root!=null){
            if(height(root.right)==h-1){
                nodes+=1<<h;
                root=root.right;
            }else{
                nodes+=1<<h-1;
                root=root.left;
            }
            h--;
        }
        return nodes;
    }

private int height(TreeNode root) {
        return root==null?-1:1+height(root.left);
    }