/**

 * 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;

 *     }

 * }

 */

//方法1：递归

class Solution {

    public int maxDepth(TreeNode root) {

        return root == null ? 0 : Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;

    }

}

//方法2：BFS，即层序遍历

//注意：队列和栈的使用，BFS用队列！

class Solution {

    public int maxDepth(TreeNode root) {

        if(root == null) {

            return 0;

        }

        int level = 0;

        //队列要初始化成LinkedList

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

        //队列添加元素用add或offer，栈用push

        queue.offer(root);

        while(!queue.isEmpty()) {

            int size = queue.size();

            level++;

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

                //队列移除元素用remove/poll，栈用pop或top

                TreeNode node = queue.poll();

                if(node.left != null) {

                    queue.offer(node.left);

                }

                if(node.right != null) {

                    queue.offer(node.right);

                }

            }

        }

        return level;

    }

}

//方法3：DFS，相当于用栈
//回溯是结束条件，做选择，移除选择

class Solution {

    private int maxLen = 0;

    public int maxDepth(TreeNode root) {

         if(root == null) {

             return 0;

         }

         dfs(root, 1);

         return maxLen;

    }

    public void dfs(TreeNode root, int level) {

        if(root == null) {

            return;

        }

        if(level > maxLen) {

            maxLen = level;

        }

        dfs(root.left, level + 1);

        dfs(root.right, level + 1);

    }

}