题解 | #判断是不是完全二叉树#

递归方式实现，完全二叉树满足以下条件

1. 0 <= 左子树深度 - 右子树深度 <= 1
2. 左子树为空，右子树一定为空
3. 左右子树都存在的情况下，左子树的右子树为空，则右子树的左子树也一定为空

/**
 * 递归方式实现
 */
public static boolean isCompleteTreeByDfs(TreeNode root) {
    if (root == null) return true;
    if (root.left == null && root.right != null)
        return false;
    if (root.left != null && root.right != null) {
        if (root.left.right == null && root.right.left != null)
            return false;
    }
    return isCompleteTreeByDfs(root.left) && isCompleteTreeByDfs(root.right);
}

public static int maxDepthByDfs (TreeNode root) {
    return root == null ? 0 : Math.max(maxDepthByDfs(root.left),
                                       maxDepthByDfs(root.right)) + 1;
}

时间复杂度 O(n)，空间复杂度 O(树的高度)