我新建的个人博客，欢迎访问：hmilzy.github.io

104.二叉树的最大深度

层序遍历和递归都行

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
        
        //递归
        if(root == null) {
            return 0;
        }
        int leftDepth = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);
        return Math.max(leftDepth,rightDepth) + 1;


        /*
        //层序遍历应用
        Deque<TreeNode> deque = new LinkedList<>();
        if(root != null) {
            deque.offer(root);
        }
        int depth = 0;
        while(!deque.isEmpty()) {
            depth++;
            int size = deque.size();
            for(int i = 0; i < size; i++) {
                TreeNode cur = deque.poll();
                
                if(cur.left != null) {
                    deque.offer(cur.left);
                }
                if(cur.right != null) {
                    deque.offer(cur.right);
                }
            }
        }
        return depth;
        */
    }
}

559.n叉树的最大深度

题目链接：n叉树的最大深度

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
    public int maxDepth(Node root) {
        
        //递归
        if(root == null) {
            return 0;
        }
        int depth = 0;
        for(Node node : root.children) {
            depth = Math.max(depth,maxDepth(node));
        }
        return depth + 1;

        /*
        //层序遍历
        Deque<Node> deque = new LinkedList<>();
        if(root != null) {
            deque.offer(root);
        }
        int depth = 0;
        while(!deque.isEmpty()) {
            int size = deque.size();
            depth++;
            for(int i = 0; i < size; i++) {
                Node cur = deque.poll();
                if(cur.children != null) {
                    for(Node node : cur.children) {
                        deque.offer(node);
                    }
                }
            }
        }
        return depth;
        */
    }
}

111.二叉树的最小深度

题目链接：二叉树的最小深度

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {

    public int minDepth(TreeNode root) {

        //递归法
        if(root == null) {
            return 0;
        }
        int leftDepth = minDepth(root.left);
        int rightDepth = minDepth(root.right);
        if(root.left == null) {
            return rightDepth + 1;
        }
        if(root.right == null) {
            return leftDepth + 1;
        }
        return Math.min(leftDepth,rightDepth) + 1;

        /*
        //迭代法，层序遍历
        if (root == null) {
            return 0;
        }
        Deque<TreeNode> deque = new LinkedList<>();
        deque.add(root);
        int depth = 0;
        while (!deque.isEmpty()) {
            int size = deque.size();
            depth++;
            for (int i = 0; i < size; i++) {
                TreeNode node = deque.poll();
                if (node.left == null && node.right == null) {
                    // 是叶子结点，直接返回depth，因为从上往下遍历，所以该值就是最小值
                    return depth;
                }
                if (node.left != null) {
                    deque.add(node.left);
                }
                if (node.right != null) {
                    deque.add(node.right);
                }
            }
        }
        return depth;
        */
    }
}

222.完全二叉树的节点个数

题目链接：完全二叉树的节点个数

个人认为还是递归法好一点。完全二叉树的方法不太能理解。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int countNodes(TreeNode root) {

        //题目是完全二叉树，肯定是有特别一些的方法的
        if (root == null) return 0;
        TreeNode left = root.left;
        TreeNode right = root.right;
        int leftDepth = 0, rightDepth = 0; // 这里初始为0是有目的的，为了下面求指数方便
        while (left != null) {  // 求左子树深度
            left = left.left;
            leftDepth++;
        }
        while (right != null) { // 求右子树深度
            right = right.right;
            rightDepth++;
        }
        if (leftDepth == rightDepth) {
            return (2 << leftDepth) - 1; // 注意(2<<1) 相当于2^2，所以leftDepth初始为0
        }
        int leftNum = countNodes(root.left);
        int rightNum = countNodes(root.right);
        int treeNum = leftNum + rightNum + 1;
        return treeNum;

        /*
        //第二种思路：递归,方法实在不错
        if(root == null) {
            return 0;
        }
        int leftNum = countNodes(root.left);
        int rightNum = countNodes(root.right);
        int treeNum = leftNum + rightNum + 1;
        return treeNum;
        */

        /*
        //第一种思路：层序遍历，直接统计数量
        Deque<TreeNode> deque = new LinkedList<>();
        if(root != null) {
            deque.offer(root);
        }
        int count = 0;
        while(!deque.isEmpty()) {
            int size = deque.size();
            count += size;
            for(int i = 0; i < size; i++) {
                TreeNode cur = deque.poll();
                if(cur.left != null) {
                    deque.offer(cur.left);
                }
                if(cur.right != null) {
                    deque.offer(cur.right);
                }
            }
        }
        return count;
        */
    }
}