二叉树深度优先遍历

深度优先遍历（Depth First Search），简称DFS，其原则是，沿着一条路径一直找到最深的那个节点，当没有子节点的时候，返回上一级节点，寻找其另外的子节点，继续向下遍历，没有就向上返回一级，直到所有的节点都被遍历到，每个节点只能访问一次。

栈（Stack），先入后出。

例如：二叉树的先序遍历（深度优先搜索实现）

首先将根节点1压入栈中【1】 将1节点弹出，找到1的两个子节点3，2，首先压入3节点，再压入2节点（后压入左节点的话，会先取出左节点，这样就保证了先遍历左节点），2节点再栈的顶部，最先出来【2，3】 弹出2节点，将2节点的两个子节点5，4压入【4，5，3】 弹出4节点，将4的子节点9，8压入【8，9，5，3】 弹出8，8没有子节点，不压入【9，5，3】 弹出9，9没有子节点，不压入【5，3】 弹出5，5有一个节点，压入10，【10，3】 弹出10，10没有节点，不压入【3】 弹出3，压入3的子节点7，6【6，7】 弹出6，没有子节点【7】  最终：{1，2，4，8，9，5，10，3，6，7 }

 

leetcode练习题：

思路：

对于每个节点，按照深度优先搜索的策略访问，同时在访问到叶子节点时更新最小深度。

从一个包含根节点的栈开始，当前深度为 1 。 然后开始迭代：弹出当前栈顶元素，将它的孩子节点压入栈中。当遇到叶子节点时更新最小深度。

1.深度优先：

public int minDepth(TreeNode root) {
    LinkedList<Pair<TreeNode, Integer>> stack = new LinkedList<>();
    if (root == null) {
      return 0;
    }
    else {
      stack.add(new Pair(root, 1));
    }
    int min_depth = Integer.MAX_VALUE;
    while (!stack.isEmpty()) {
      Pair<TreeNode, Integer> current = stack.pollLast();
      root = current.getKey();
      int current_depth = current.getValue();
      if ((root.left == null) && (root.right == null)) {
        min_depth = Math.min(min_depth, current_depth);
      }
      if (root.left != null) {
        stack.add(new Pair(root.left, current_depth + 1));
      }
      if (root.right != null) {
        stack.add(new Pair(root.right, current_depth + 1));
      }
    }
    return min_depth;
  }

2：递归

class Solution {
  public int minDepth(TreeNode root) {
    if (root == null) {
      return 0;
    }
    if ((root.left == null) && (root.right == null)) {
      return 1;
    }
    int min_depth = Integer.MAX_VALUE;
    if (root.left != null) {
      min_depth = Math.min(minDepth(root.left), min_depth);
    }
    if (root.right != null) {
      min_depth = Math.min(minDepth(root.right), min_depth);
    }
    return min_depth + 1;
  }
}