二叉树遍历方式

• 深度优先：前序、中序、后序
• 广度优先：层序遍历
• 说明：
  前序遍历【中、左、右】：先访问中间节点，再访问左孩子，再访问右孩子。左、右孩子分别也是前序
  中序遍历【左、中、右】：
  后序遍历【左、右、中】
  遍历：递归 & 非递归【递归的实现–>栈，所以非递归借助栈实现】
  代码实现如下：
  1-（1）递归 – 前序

import java.util.ArrayList;
/**- Definition for a binary tree node.- public class TreeNode {-     int val;-     TreeNode left;-     TreeNode right;-     TreeNode() {}-     TreeNode(int val) { this.val = val; }-     TreeNode(int val, TreeNode left, TreeNode right) {-         this.val = val;-         this.left = left;-         this.right = right;-     }- }*/
class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();preOrder(root,result);return result;}void preOrder(TreeNode root,List<Integer> result){if (root == null) return ;result.add(root.val);// 中preOrder(root.left,result);//左preOrder(root.right,result);// 右
}    
}

1-（2）非递归-前序

class Solution {public List<Integer> preorderTraversal(TreeNode root) {//非递归实现Stack<TreeNode> st = new Stack<>();List<Integer> res = new ArrayList<>();if (root == null) return res;st.push(root);while (!st.empty()){//中TreeNode node = st.peek();st.pop();res.add(node.val);if (node.right != null) st.push(node.right); // 右if (node.left != null) st.push(node.left);//左}return res;
}   
}

说明：

• 递归的实现中，前、中、后有统一的编码方式，只需要将递归函数中中、左、右逻辑调换顺序即可

• 非递归：借用栈实现
  1）前序：中、左、右。所以访问到一个节点，将其入栈【先进后出】，后处理节点【加入结果集合中】
  访问顺序：由于栈的先进后出，所以是先访问右孩子，入栈、处理；再访问左孩子、入栈、处理；
  2）后序：左右中
  【前序】中左右 --（调换左、右顺序）–>中右左–>反转操作–>左右中【即后序】

2-（1）递归–后序

class Solution {public List<Integer> postorderTraversal(TreeNode root) {//1、递归算法List<Integer> result = new ArrayList<>();postorder(root,result);return result;}void postorder(TreeNode root,List<Integer> result){//递归终止条件if (root == null) return;postorder(root.left,result);postorder(root.right,result);result.add(root.val);}
}

2-（2）非递归-后序

class Solution {public List<Integer> postorderTraversal(TreeNode root) {// 非递归- 后序【左、右、中】//前序：中左右-->中右左-(反转)->左右中//数组反转的实现：双指针、库函数中的reverseStack<TreeNode> st = new Stack<>();List<Integer> res = new ArrayList<>();if (root == null) return res;st.push(root);while (!st.empty()){//中TreeNode node = st.peek();st.pop();res.add(node.val);if (node.left != null) st.push(node.left);//左if (node.right != null) st.push(node.right); // 右   }//res进行反转Collections.reverse(res);return res;}
}

3-(1) 递归-中序

class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();inorder(root,result);return result;}void inorder(TreeNode root,List<Integer> result){if(root == null) return; inorder(root.left,result);//左result.add(root.val); //中inorder(root.right,result); //右}
}

3-(2）非递归-中序

class Solution {public List<Integer> inorderTraversal(TreeNode root) {// 非递归中序遍历：左中右//访问顺序，与处理顺序不一致//栈：记录访问过的节点// 指针：遍历二叉树List<Integer> result = new ArrayList<>();Stack<TreeNode> st = new Stack<>();TreeNode cur = root;// 指针：遍历while (cur != null || !st.empty()){ //cur==null&& st.empty()使停止循环，注意在while中是||if (cur != null){st.push(cur);cur = cur.left;}else {cur = st.peek();st.pop();result.add(cur.val);cur = cur.right;}   }return result;}      
}