DFS（Depth-First Search）

DFS 是一种递归形式的搜索方式。相对于“层”的概念，DFS更偏向于“垂直”的概念。

Top Down vs. Bottom Up

Top Down DFS

• 把值通过参数的形式从上往下传
• 一般dfs()本身不返回值

Bottom Up DFS(更难也更常见)

• 把值从下（subproblem）往上传
• 当前递归层利用subproblem传上来的值计算当前层的新值并返回
• 一定会有返回值

一般步骤

1. Base Case
2. 向子问题要答案（return value）
3. 利用子问题的答案构建当前问题（当前递归层）的答案
4. 若有必要，做一些额外操作
5. 返回答案（给父问题）（第2步和第5步返回的值是一样的）

实例

/*
给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明:叶子节点是指没有子节点的节点。

示例：
给定二叉树 [3,9,20,null,null,15,7]，

    3
   / \
  9  20
    /  \
   15   7
返回它的最大深度3 。

 */
public class LeetCode104 {

    public static void main(String[] args) {
        Solution solution = new Solution();
        TreeNode node0 = TreeNode.buildBinaryTree(new Integer[]{1, 2, 2, null, 3, null, 3});
        System.out.println(solution.maxDepth(node0));
        System.out.println(new Solution2().maxDepth(node0));
    }

    /*
    DFS 深度优先搜索策略
     */
    static class Solution {
        public int maxDepth(TreeNode root) {
            if (root == null) {
                return 0;
            } else {
                int left_height = maxDepth(root.left);
                int right_height = maxDepth(root.right);
                return java.lang.Math.max(left_height, right_height) + 1;
            }
        }
    }


    static class Solution2 {
        public int maxDepth(TreeNode root) {
            Queue<Pair<TreeNode, Integer>> stack = new LinkedList<>();
            if (root != null) {
                stack.add(new Pair(root, 1));
            }

            int depth = 0;
            while (!stack.isEmpty()) {
                Pair<TreeNode, Integer> current = stack.poll();
                root = current.first;
                int current_depth = current.second;
                if (root != null) {
                    depth = Math.max(depth, current_depth);
                    stack.add(new Pair(root.left, current_depth + 1));
                    stack.add(new Pair(root.right, current_depth + 1));
                }
            }
            return depth;
        }
    }
}