二叉树的深搜和广搜

二叉树是计算机中一个重要的数据结构，在这里主要谈一下二叉树的深度优先搜索(DFS)和广度优先搜索(BFS)。

所谓DFS，就是沿着树的深度一直往下，一直到达一个叶子节点，然后再返回遍历剩余的节点。根据树的性质，树结构不存在环，因此遍历的时候不需要标记。如果在遍历一个图的时候，因为图中有环的存在，因此需要标记访问过的节点，以防止程序进入死循环。言归正传，树的DFS有三种方式，分别为：前序遍历，中序遍历，和后序遍历。根据这个性质，我们很容易想到用堆栈完成DFS。遍历的时候我们将元素压栈，利用堆栈后进先出的性质来实现不同的遍历。

所谓前序遍历，就是每次都先访问根节点，然后依次为左子树，和右子树。根据前序遍历的规定，左子树先于右子树，依次压栈的时候从右子树开始。代码如下：

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
 }

public class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        if(root == null) return list;
        stack.push(root);

        while(!stack.empty()) {
            TreeNode node = stack.pop();
            list.add(node.val);
            if(node.right != null) 
                stack.push(node.right);
            if(node.left != null)
                stack.push(node.left);
        }
        return list;
    }
}

中序遍历是从左子树开始，然后依次为根节点，右子树，注意这里的根节点是指的每个子树的根结点。代码如下：

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
 }

public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        if (root == null) return list;
        while(!stack.empty() || root != null) {
            if(root != null){
                stack.push(root);
                root = root.left;
            } else {
                root = stack.pop();
                list.add(root.val);
                root = root.right;
            }
        }
        return list;
 }

后序遍历是先遍历左子树，然后依次为右子树，根节点。因为根节点在最后遍历，所以在程序完成时如果按照左右根的方式会比较繁琐。我们不妨换一下思路，在完成前序遍历后，我们发现前序遍历是根->左->右，后序遍历时左->右->根，如果我们按照根->右->左的方式进行遍历，然后把结果倒转，就是左->右->根了。代码如下：

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
 }

  public List<Integer> postorderTraversal(TreeNode root) {
        LinkedList<Integer> list = new LinkedList<Integer>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        if(root == null)
            return list;
        stack.push(root);
        while(!stack.empty()) {
            TreeNode node = stack.pop();
            list.addFirst(node.val);
            if(node.left != null)
                stack.push(node.left);
            if(node.right != null)
                stack.push(node.right);
        }
        return list;
 }

以上我们介绍了二叉树的三种遍历方式，它们都属于深度优先遍历，对于深度优先遍历，我们都用堆栈实现。接下来我们介绍一下二叉树的广度优先遍历。

BFS，即广度优先遍历，它时沿着树的宽度进行遍历，从第一层直到最后一层，一直到遍历完树中所有的节点。对于BFS，我们通常用队列来实现，队列先进先出的性质正好满足BFS的要求。
我们先从根节点开始，然后加入到队列中，依次为左子树，右子树，然后每次从队列中取出一个节点，都一次访问它的左孩子和右孩子，直到遍历完所有的节点。代码如下：

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
 }

public void BFS(TreeNode root) {
	List<Integer> list = new ArrayList<Integer>();
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        if(root == null) return list;
        queue.offer(root);
        
        while(!queue.isEmpty()) {
            TreeNode node = queue.poll();
            list.add(node.val);
            if(node.left != null)
                queue.offer(node.left);
            if(node.right != null)
                queue.offer(node.right);
        }
        return list;
}