DAY16|104.二叉树的最大深度，111.二叉树的最小深度，222完全二叉树的个数

104.二叉树的最大深度

思路：

1、此题有两种求解方式，一种是求根节点的高度，另一种是求二叉树的深度；如果求根节点的高度，则需要从叶子节点开始往上回溯，那么这一题和昨天的"对称二叉树"一题的思想如出一辙，通过后序遍历的思想，借助递归完成；

2、通过求二叉树深度的方式，则需要类似于昨天"二叉树的层级遍历"方式类似，使用前序遍历的思想，借助队列的方式完成求解；

3、求高度的递归代码可以深刻体现后序遍历的作用，可以帮助我们自顶而上求解二叉树；

代码：

//后序遍历的
class Solution {
    public int maxDepth(TreeNode root) {
        return getHight(root);
    }

    public int getHight(TreeNode node) {
        //说明此时已经递归到叶子节点的子节点了，叶子节点高度为1，那么他的子节点为null的话，即为0
        if (node == null) return 0;
        //左子节点的高度
        int leftHight = getHight(node.left);
        //右子节点的高度
        int rightHight = getHight(node.right);
        int hight = Math.max(leftHight, rightHight) + 1;
        return hight;
    }
}

// 前序遍历，迭代法，借助队列二叉树深度
class Solution {
    public int maxDepth(TreeNode root) {
        if (root== null) {
            return 0;
        }
        int depth = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            depth++;
            int len = queue.size();
            while (len > 0) {
                TreeNode poll = queue.poll();
                if (poll.left != null) {
                    queue.offer(poll.left);
                }
                if (poll.right != null) {
                    queue.offer(poll.right);
                }
                len--;
            }
        }
        return depth;
    }
}

111.二叉树的最小深度

思路：

1、此题和上题的思路差不多，需要注意区分左右子树有一个为空的情况；

代码：

class Solution {
    public int minDepth(TreeNode root) {
        return getMinHight(root);
    }

    public int getMinHight(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int leftMinHight = getMinHight(node.left);
        int rightMinHight = getMinHight(node.right);
        if (node.left == null && node.right != null) {
            return rightMinHight + 1;
        } else if (node.left != null && node.right == null) {
            return leftMinHight + 1;
        } else {
            return Math.min(leftMinHight, rightMinHight) + 1;
        }
    }
}

222.完全二叉树的个数

思路：

1、完全二叉树可以利用其特性实现个数计算；

代码：

//利用完全二叉树的特性
class Solution {
    public int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return getNum(root);
    }

    public int getNum(TreeNode node) {
        if (node == null) return 0;
        TreeNode leftNode = node.left;
        TreeNode rightNode = node.right;
        int leftDepth = 0;
        int rightDepth = 0;
        while (leftNode != null) {
            leftNode = leftNode.left;
            leftDepth++;
        }
        while (rightNode != null) {
            rightNode = rightNode.right;
            rightDepth++;
        }
        if (leftDepth == rightDepth) {
            return (2<<leftDepth) - 1;
        }
        //如果不相同
        int leftCount = getNum(node.left);
        int rightCount = getNum(node.right);
        return leftCount + rightCount + 1;
    }
}

class Solution {
    public int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }
        //使用迭代遍历完成
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int count = 0;
        while (!queue.isEmpty()) {
            int len = queue.size();
            while (len > 0) {
                TreeNode poll = queue.poll();
                count++;
                if (poll.left != null) {
                    queue.offer(poll.left);
                }
                if (poll.right != null) {
                    queue.offer(poll.right);
                }
                len--;
            }
        }
        return count;
    }
}