二叉树的遍历

问题重述：

二叉树的遍历

问题分析：

解法：

递归、迭代

解题：

代码：

递归写法

//前序遍历
 public List preorder(TreeNode root,List list){
        if(root == null){
            return list;
        }
        list.add(root.val);
        preorder(root.left,list);
        preorder(root.right,list);
        return list;
    }
// 中序遍历
public List preorder(TreeNode root,List list){
        if(root == null){
            return list;
        }
        
        preorder(root.left,list);
        list.add(root.val);
        preorder(root.right,list);
        return list;
    }
// 后续遍历
public List preorder(TreeNode root,List list){
        if(root == null){
            return list;
        }
        
        preorder(root.left,list);
        
        preorder(root.right,list);
        list.add(root.val);
        return list;
    }

代码解析：

递归是我们常用的简化操作的方法，使用递归的时候，隐式的使用了一个栈（方法栈）。递归的本质就是自己调用自己。使用递归的时候，我们只需要明白三件事：

递归终止条件：递归不能无限的进行下去，我们必须要有结束递归的条件，否则方法栈会溢出，一般我们都是根据题目条件找到递归的结束条件，像二叉树的遍历，如果当前结点为null，肯定就不能继续递归下去了，就得要返回了。

递归过程中重复的操作（也就是当前递归要做的事）：这个是每个方法执行都需要执行的操作，比如记录路径或者进行运算等操作

如何进入下一次递归（也就是递归的顺序）：我们的递归中的参数一定是不断变化的，否则我们的方法会在同一个地方不断的运行，而无法达到递归的终止条件，如果有多个递归，进入下一次递归的变化条件也就决定了递归的顺序。

非递归写法

//前序遍历
public List preorder(TreeNode root,List list){
        /*if(root == null){
            return list;
        }
        list.add(root.val);
        preorder(root.left,list);
        preorder(root.right,list);*/
        Stack stack = new Stack();
        while(!stack.isEmpty() || root != null){
            if(root != null){
                list.add(root.val);
                stack.push(root);
                root = root.left;
            }else{
                root = stack.pop().right;
            }
        }
        return list;
    }
// 中序遍历
public List preorder(TreeNode root,List list){
        Stack stack = new Stack();
        while(!stack.isEmpty() || 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 List preorder(TreeNode root,List list){
        if(root == null){
            return list;
        }
        Stack stack = new Stack();
        stack.push(root);
        TreeNode curPre = null;
        while(!stack.isEmpty()){
        	curPre = stack.peek();
            if(curPre.left != null && root != curPre.left && root != curPre.right) {
            	stack.push(curPre.left);
            }else if(curPre.right != null && root != curPre.right){
            	stack.push(curPre.right);
            }else {
            	list.add(stack.pop().val);
            	root = curPre;
            }
        }
        return list;
    }

代码解析：

前序遍历：因为前序遍历的顺序是根->左->右，因此，我们每次遍历一个结点就将该节点的值记录下来，然后对该节点的下一个接左节点进行操作（需要注意的是，在我们对下一个结点进行操作的之前，我们需要保存当前结点，因为我们还需要遍历当前节点的右节点，把该节点加入栈中保存即可）。当左子结点都遍历完成后，此时的root应该指向的是当前二叉树分支的最左边结点的左子节点（为null），此时我们就需要得到当前为null结点的右边兄弟结点了（这个结点需要通过父节点获得，我们从栈中弹出的结点就是右边节点的父节点），对每一个结点都重复上面的步骤，遍历完所有的结点，顺序就是先序遍历的顺序了。

中序遍历：中序遍历的顺序为：左->根->右，操作和前序遍历的操作很相似，都是利用一个栈来辅助操作，通过while循环来遍历每一个结点。但是和前序遍历的不一样的地方在于，我们记录结点的值的时候是在从栈中弹出结点的时候（因为弹出的结点此时一定是当前二叉树分支的最左边结点，也可能是根结点（是根节点的时候说明当前节点已经没有左子节点了）），此时记录当前结点的值，然后再对当前节点的右子节点进行上述操作，就实现了对二叉树的中序遍历。

后序遍历：后序遍历的顺序左->右->根，后序遍历相较前序遍历和中序遍历比较复杂，不能直接通过简单的循环解决，因为我们的根节点需要经过多次，第一次经过根节点找到左节点，第二次通过根节点找到右节点，第三次找到根节点本身，如果我们使用前序遍历和中序遍历的方式是解决不了的。后序遍历的非递归解决方式有两种，一种使用两个栈来解决，一种使用一个栈解决

• 后序遍历方法一：使用两个栈，一个栈A存入头节点，每一次弹出结点的时候，就将当前结点存入栈B，并且将当前节点的左子节点和右子节点分别存入栈A中，重复上面的操作，等到栈A为空的时候，栈B内从栈顶到栈底就是后序遍历的顺序了。然后将栈按顺序弹出处理结果就可以。
• 后序遍历方法二：当我们使用一个栈的时候，我们就需要考虑，在什么时候，将当前结点的值保存起来，显而易见，是当当前结点为叶子结点（也可以是当前节点的左右子树都已经遍历过了），我们可以创建一个结点用来保存当前结点的父节点，如果父节点的左右结点都没有被遍历过，遍历父节点的左子节点，如果左子节点被遍历过就去遍历父节点的右子节点，如果当前结点的左右结点都被遍历过，将当前父节点记录，找到当前节点的父节点（当前结点就用于判断是否被遍历过），重复上述操作。（使用这个方法有一个问题，那就是二叉树必须有节点，否则会报空指针异常，我们需要对树为空进行特别处理）