题解 | #二叉树的最大深度#

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param root TreeNode类
     * @return int整型
     */
    public int maxDepth2 (TreeNode root) {
        // write code here
        if (root == null)
            return 0;
        return Math.max(maxDepth2(root.left), maxDepth2(root.right)) + 1;
    }
    public int maxDepth3(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        int maxdep = Integer.MIN_VALUE, dep = 0;
        TreeNode pre = null;

        if (root == null)
            return 0;

        while (true) {
            while (root != null && root != pre) {
                stack.push(root);
                dep++;
                if (dep > maxdep)
                    maxdep = dep;
                root = root.left;
            }
            if (!stack.empty()) {
                root = stack.pop();
                dep--;
            } else {
                break;
            }
            if (root.right != null && pre != root.right) {
                stack.push(root);
                dep++;
                if (dep > maxdep)
                    maxdep = dep;
                root = root.right;
            } else {
                pre = root;
            }
        }

        return maxdep;
    }
    public int maxDepth(TreeNode root) {
        int dep = 0;
        Deque<TreeNode> queue1 = new ArrayDeque<>();
        Deque<TreeNode> queue2 = new ArrayDeque<>();
        if (root == null)
            return 0;

        queue1.push(root);
        dep++;
        while (!queue1.isEmpty() || !queue2.isEmpty()) {
            if (!queue1.isEmpty()) {
                while (!queue1.isEmpty()) {
                    root = queue1.pop();
                    if (root.left != null)
                        queue2.push(root.left);
                    if (root.right != null)
                        queue2.push(root.right);
                }
                if (!queue2.isEmpty())
                    dep++;
            } else {
                while (!queue2.isEmpty()) {
                    root = queue2.pop();
                    if (root.left != null)
                        queue1.push(root.left);
                    if (root.right != null)
                        queue1.push(root.right);
                }
                if (!queue1.isEmpty())
                    dep++;
            }
        }
        return dep;
    }
}