1. 递归法

递归的三大要素

确定递归函数的参数和返回值： 确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数，并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
确定终止条件： 写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。

确定单层递归的逻辑： 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。

1.1 前序遍历

```java public class PreorderTraversal { ArrayList preOrderReverse(TreeNode root) {

 ArrayList<Integer> integers = new ArrayList<>();
 preOrder(root,integers);
 return integers;

}

void preOrder(TreeNode root , ArrayList arrayList) {

 //递归的中止条件
 if (root == null) {
     return;
 }
 //先序遍历在上面 中序在中间 下序在下面
 arrayList.add(root.val);
 //依次递归调用左子树 左子树接着遍历
 preOrder(root.left, arrayList);
 //左子树遍历完 遍历右子树
 preOrder(root.right, arrayList);

} }

中序后序改变add的位置即可
<a name="PgJyF"></a>
# 2. 迭代法
<a name="DHr17"></a>
## 2.1 前序遍历
前序遍历输出顺序为 中 -> 左 -> 右 压入顺序为 中 -> 右 -> 左
```java
public class IterationPreorderTraversal {
    public List<Integer> preorderTraversal(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Stack<TreeNode> stack = new Stack<>();
        //栈首先push进root
        stack.push(root);
        //如果栈不为空就循环
        while (!stack.isEmpty()) {
            //干了两件事情 1 将栈顶弹出 2将弹出的值赋给了temp
            TreeNode temp = stack.pop();
            //将弹出的temp的值放到res队列中
            res.add(temp.val);
            //如果temp的右子节点不为空 就将它push入栈 之所以要先右边是因为弹出的时候先弹出左边
            if (temp.right != null) {
                stack.push(temp.right);
            }
            //左边同理 如果父节点的两个子节点都不为空 先弹出的是左节点 左节点弹出后 这时temp变成了左节点 直到左子树遍历完才遍历当前的右子树
            if (temp.left != null) {
                stack.push(temp.left);
            }
        }
        return res;
    }
}

2.2 中序遍历

class Solution {
        public List<Integer> inorderTraversal(TreeNode root) {
            ArrayList<Integer> res = new ArrayList<>();
            if (root == null) {
                return res;
            }
            Stack<TreeNode> stack = new Stack<>();
            TreeNode temp = root;
            //当栈不等于空(当左子树和根节点都遍历完的时候栈等于空 这时还有右子树没有遍历 就需要在判断树节点不等于空) 树节点不等于空的时候
            while (!stack.isEmpty() || temp != null) {
                //如果树节点不等于空就将当前节点push入栈 再使当前节点为当前节点的左子节点直到到了最左边为空
                if (temp != null) {
                    stack.push(temp);
                    temp = temp.left;
                } else {
                    //temp为空代表没有左子树 将当前栈顶弹出 并赋给temp 将temp加到res中
                    temp = stack.pop();
                    res.add(temp.val);
                    //temp往右子树遍历
                    temp = temp.right;
                }
            }
            return res;
        }
    }

2.3 后序遍历

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode temp = stack.pop();
            res.add(temp.val);
            if (temp.left != null) {
                stack.push(temp.left);
            }
            if (temp.right != null) {
                stack.push(temp.right);
            }
        }
        Collections.reverse(res);
        return res;
    }
}

3. 迭代法的统一遍历方法

3.1 前序遍历

class Solution {
        public List<Integer> preorderTraversal(TreeNode root) {
            ArrayList<Integer> res = new ArrayList<>();
            Stack<TreeNode> stack = new Stack<>();
            if (root != null) {
                stack.push(root);
            }
            while (!stack.isEmpty()) {
                TreeNode node = stack.peek();
                if (node != null) {
                    stack.pop();
                    if (node.right != null) {
                        stack.push(node.right);
                    }
                    if (node.left != null) {
                        stack.push(node.left);
                    }
                    stack.push(node);
                    stack.push(null);
                } else {
                    stack.pop();
                    node = stack.peek();
                    stack.pop();
                    res.add(node.val);
                }
            }
            return res;
        }
    }

压入顺序右左中

3.2 中序遍历

class Solution {
        public List<Integer> inorderTraversal(TreeNode root) {
            //返回结果
            ArrayList<Integer> res = new ArrayList<>();
            Stack<TreeNode> stack = new Stack<>();
            //如果根节点!=null就push
            if (root!=null) {
                stack.push(root);
            }
            //循环 直到栈=null
            while (!stack.isEmpty()) {
                //peek栈 得到栈顶元素
                TreeNode node = stack.peek();
                //如果栈顶!=null 就将栈顶弹出 并且按照右中左的顺序放入栈 压入中间的时候需要再压入一个null
                if (node != null) {
                    stack.pop();// 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
                    if (node.right != null) {
                        stack.push(node.right);
                    }
                    stack.push(node);
                    stack.push(null);// 中节点访问过，但是还没有处理，加入空节点做为标记。
                    if (node.left != null) {
                        stack.push(node.left);
                    }
                } else {// 只有遇到空节点的时候，才将下一个节点放进结果集
                    stack.pop(); //弹出空节点
                    node = stack.peek();
                    stack.pop();
                    res.add(node.val);
                }
            }
            return res;
        }
    }

压入顺序右中左

3.3 后序遍历

class Solution {
        public List<Integer> inorderTraversal(TreeNode root) {
            //返回结果
            ArrayList<Integer> res = new ArrayList<>();
            Stack<TreeNode> stack = new Stack<>();
            //如果根节点!=null就push
            if (root!=null) {
                stack.push(root);
            }
            //循环 直到栈=null
            while (!stack.isEmpty()) {
                //peek栈 得到栈顶元素
                TreeNode node = stack.peek();
                //如果栈顶!=null 就将栈顶弹出 并且按照右中左的顺序放入栈 压入中间的时候需要再压入一个null
                if (node != null) {
                    stack.pop();// 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
                    stack.push(node);
                    stack.push(null);// 中节点访问过，但是还没有处理，加入空节点做为标记。
                    if (node.right != null) {
                        stack.push(node.right);
                    }
                    if (node.left != null) {
                        stack.push(node.left);
                    }
                } else {// 只有遇到空节点的时候，才将下一个节点放进结果集
                    stack.pop(); //弹出空节点
                    node = stack.peek();
                    stack.pop();
                    res.add(node.val);
                }
            }
            return res;
        }
    }

后序遍历中右左

数据结构与算法

二叉树的遍历