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

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 {
    private class NodeDeep {
        TreeNode node;
        int depth;
        NodeDeep(TreeNode node, int depth) {
            this.node = node;
            this.depth = depth;
        }
    }

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    public int maxDepth (TreeNode root) {
        // write code here
        return maxDepthRecursively(root);
        //return maxDepthByLoop(root);
    }

    private int maxDepthRecursively (TreeNode root) {
        // write code here
        if(root==null) {
            return 0;
        }
        int subLeft = maxDepthRecursively(root.left);
        int subRight = maxDepthRecursively(root.right);
        return (subLeft > subRight ? subLeft : subRight) + 1;
    }

    private int maxDepthByLoop(TreeNode root) {
        if(null == root) return 0;
        int ans = 0;
        Deque<NodeDeep> deque = new ArrayDeque<>();
        NodeDeep head = new NodeDeep(root, 1);
        deque.push(head);
        while(!deque.isEmpty()) {
            NodeDeep nodeDeep = deque.removeFirst();
            ans = nodeDeep.depth;
            if(null != nodeDeep.node.left) {
                NodeDeep leftNodeDeep = new NodeDeep(nodeDeep.node.left, nodeDeep.depth+1);
                deque.push(leftNodeDeep);
            }
            if(null != nodeDeep.node.right) {
                NodeDeep rightNodeDeep = new NodeDeep(nodeDeep.node.right, nodeDeep.depth+1);
                deque.push(rightNodeDeep);
            }
        }

        return ans;

    }
}