树的遍历

树的遍历方式主要分为四种，先序、中序、后序和层序，在这篇博客中我将仔细介绍一下树的这四种遍历方式。

先序遍历

先序遍历，也叫先根遍历、前序遍历，首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树，如果二叉树为空则返回。可以简记为根左右。
以上图为例，整体的遍历过程为：

• 先遍历A节点
• 然后遍历A的左子节点B节点
• 接着遍历B节点的左子节点D节点
• D节点没有左子节点和右子节点，然后我们回溯到B节点，遍历B节点的右子节点E节点
• 同理E没有左子节点和右子节点，我们继续回溯到B节点，发现B节点的左右子节点都已被访问，再接着回溯到B的父节点A。
• 遍历A节点的右节点C
• 遍历C的左子节点F，F没有左右子节点，回溯到C节点，C节点没有右子树，回溯到A节点，此使所有的节点都已被访问完毕。
• 遍历结果为：ABDECF

代码实现

树先序遍历的实现方式主要包括两种，递归和迭代，递归算法调用隐式栈，而迭代算法显式的调用栈。

递归实现

//根左右，先访问根节点，然后访问左子树，最后再访问右子树
public List<Integer> preorderTraversal(TreeNode root){
        List<Integer> res = new ArrayList<>();
        preorder(root,res);
        return res;
    }

    private void preorder(TreeNode root, List<Integer> res) {
        if(root == null) return;
        res.add(root.val);
        preorder(root.left,res);
        preorder(root.right,res);
    }

迭代实现

先序遍历的迭代实现要借用数据结构栈，首先我们要知道栈这种数据结构是先进后出，所以我们入栈的时候要先压入最右的节点，然后依次从右往左压入节点，这样就能保证出栈的时候首先访问左节点。以上图为例整体的遍历流程如下：

• 初始化一个列表res用来存放访问结果
• 首先将根节点A压入栈中，此时栈中只有元素A，stack(A)
• 我们将A节点出栈，存入到res中，将A的子节点依次从右到左压入栈中，此时栈顶元素为B,栈中的元素为stack(B,C)
• 然后B节点出栈，存入res中，将B节点的子节点依次从右到左压入栈中，此使栈顶元素为D，栈中的元素为stack(D,E,C)
• 然后我们将D节点出栈存入到res中，因为D节点为叶节点没有子节点，所以此时的栈顶元素为E，栈中元素为stack(E,C)
• 重复上述过程，直到栈空位置，遍历结束，返回res列表，即为访问结果

public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
        ArrayList<Integer> res=new ArrayList<Integer>();
        if(root==null)
            return res;
        Stack<TreeNode> stack=new Stack<TreeNode>();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode tree=stack.pop();　　　　　　//先往栈中压入右节点，再压左节点，这样出栈就是先左节点后右节点了。
            if(tree.right!=null)
                stack.push(tree.right);
            if(tree.left!=null)
                stack.push(tree.left);
            res.add(tree.val);
        }
        return res;
    }

中序遍历

中序遍历，也叫中根遍历，遍历方式可以简记为左根右。首先访问左子树，然后访问根节点，最后遍历右子树，若二叉树为空结束访问，否则：

• 中序遍历左子树
• 访问根节点
• 中序遍历右子树
  具体流程如下：
• 初始化res列表存储访问结果
• 首先访问根节点A的左子树BDE
• 发现B也有左右子树，那么我们先访问B的左子树D
• D没有左子树，所以我们先将D存入res列表中
• 根据左根右的思想，然后我们访问D节点的根节点B，将B存入res列表中
• 然后DB都访问过了，即左根都被访问了，接着我们访问B节点的右子树E
• 因为E没有左子树，所以将E存入res列表中，判断发现E也没有右子树，我们回溯到B节点，发现B的左右节点都已被访问，我们回溯到A节点，将A节点存入列表中
• 整棵树的左子树和根节点均已被访问，接着访问根节点A的右子树。
• 重复上述过程，直到访问完所以的节点。

上图的访问结果为：DBEAFC

代码实现

递归实现

public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        inorder(root,res);
        return res;

    }

    private void inorder(TreeNode root, List<Integer> res) {
        if(root == null) return;
        inorder(root.left,res);
        res.add(root.val);
        inorder(root.right,res);
        
    }

迭代实现

中序遍历的迭代实现要依靠栈数据结构，有一个口诀就是中序遍历不忘“左链入栈”

public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        if(root == null) return res;
        /*退出循环的条件，root != null没有特殊含义，只是让循环得以进行下去，
        循环的终止条件只要是判断栈空不空所决定*/
        while (root != null || !stack.isEmpty())
        {
            while (root != null)    //左链入栈
            {
                stack.push(root);
                root = root.left;
            }
            TreeNode node = stack.pop();  //左子树为空将根节点出栈
            res.add(node.val);
            root = node.right;   //访问右子树

        }
        return res;

    }

后序遍历

后序遍历（LRD），也叫做后根遍历，可记做左右根。后序遍历有递归算法和非递归算法两种。在二叉树中，先左后右再根，即首先遍历左子树，然后遍历右子树，最后访问根结点。

• 后序遍历左子树

• 后序遍历右子树

• 访问根结点
  以上图为例我们走一遍整体的遍历流程：

• 初始化res列表存储遍历结果

• 首先访问根节点A的左子树BDE

• 发现节点B也有左右子树，那我们访问B节点的左子树D

• D节点没有左右子树，所以将D节点存入到res列表中

• 接着我们回溯到B节点，发现其存在右子树E，那我们先访问E节点

• E节点没有左右子树，我们将E节点存入res列表中

• 此使B节点的左右子树访问完毕，我们将B节点存入res中，此时节点A的左子树访问完毕，我们访问其右子树。

• 右子树仍然按照左右跟的思想进行遍历。

• 最后在访问根节点A，至此遍历结束

代码实现

代码实现主要包括两种：

• 递归实现
• 迭代实现

递归实现

public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        postorder(root, res);
        return res;
    }

    public void postorder(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }
        postorder(root.left, res);   //遍历左子树
        postorder(root.right, res);  //遍历右子树
        res.add(root.val);           //访问根节点
    }

迭代实现

public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        if (root == null) {
            return res;
        }

        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        TreeNode prev = null;
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            //pre用来标记上一次右子树是否已经访问过
            if (root.right == null || root.right == prev) {
                res.add(root.val);
                prev = root;
                root = null;
            } else {
                stack.push(root);
                root = root.right;
            }
        }
        return res;


    }