/**

 * Definition for a binary tree node.

 * public class TreeNode {

 *     int val;

 *     TreeNode left;

 *     TreeNode right;

 *     TreeNode(int x) { val = x; }

 * }

 */

class Solution {

    public int maxDepth(TreeNode root) {

// 递归

        // if (null == root) {

        //     return 0;

        // }

        // if (null == root.left && null == root.right) {

        //     return 1;

        // }

        // if (maxDepth(root.left) >= maxDepth(root.right)) {

        //     return 1 + maxDepth(root.left);

        // } else {

        //     return 1 + maxDepth(root.right);

        // }

        
// 非递归

        if (null == root) {

            return 0;

        }

        if (null == root.left && null == root.right) {

            return 1;

        }

        int depth = 0;

        Queue<TreeNode> queue = new ArrayDeque<>();

        queue.add(root);

        while (queue.size()>0){

            int index = queue.size();

            depth++;

            for (int i=0;i<index;i++){

                TreeNode node =  queue.remove();

                if (null != node.left || null != node.right){

                    if (null != node.left){

                        queue.add(node.left);

                    }

                    if (null != node.right){

                        queue.add(node.right);

                    }

                }

            }

        }

        return depth;

    }

}