二叉树的遍历 - 你不懂诶
source link: https://www.cnblogs.com/lzdream/p/16987997.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
1.二叉树的遍历
二叉树主要有两种遍历方式：
深度优先遍历：先往深走，遇到叶子节点再往回走。
- 前序遍历（递归法，迭代法） 中左右
- 中序遍历（递归法，迭代法） 左中右
- 后序遍历（递归法，迭代法） 左右中
广度优先遍历：一层一层的去遍历。
- 层次遍历（迭代法）
对比图可以理解一下遍历的过程，前中后序遍历涉及递归和迭代两种方法讲解。
2.LeetCode链接
前序遍历：https://leetcode.cn/problems/binary-tree-preorder-traversal/submissions/
中序遍历：https://leetcode.cn/problems/binary-tree-inorder-traversal/submissions/
后序遍历：https://leetcode.cn/problems/binary-tree-postorder-traversal/submissions/
层序遍历：https://leetcode.cn/problems/binary-tree-level-order-traversal/submissions/
感兴趣的可以去练练手！！！
3.前序遍历
前序遍历的顺序是中左右，即先根节点、左子树、右子树，那么我们先考虑递归进行求解。
要打印出前序遍历节点的数值，所以参数里需要放节点的数值，除了这一点就不需要在处理什么数据了也不需要有返回值，所以递归函数返回类型就是void。
Traversal(TreeNode root, List<Integer> list)
当前遍历的节点是空了，那么本层递归就要要结束了，所以如果当前遍历的这个节点是空，就直接return。
if (cur == NULL) return;
前序遍历是中左右的循序，所以在单层递归的逻辑，是要先取中节点的数值。
list.add(root.val);
Traversal(root.left, list);
Traversal(root.right, list);
所以总体的递归代码如下：
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<Integer>();
preorder(root, result);
return result;
}
public void preorder(TreeNode root, List<Integer> result) {
if (root == null) {
return;
}
result.add(root.val);
preorder(root.left, result);
preorder(root.right, result);
}
}
对于迭代法，难度会更大一点！！！
前序遍历是中左右，每次先处理的是中间节点，那么先将根节点放入栈中，然后将右孩子加入栈，再加入左孩子。为什么要先加入 右孩子，再加入左孩子呢？ 因为这样出栈的时候才是中左右的顺序。
所以我们不难写出代码如下：
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null){
return result;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()){
TreeNode node = stack.pop();
result.add(node.val);
if (node.right != null){
stack.push(node.right);
}
if (node.left != null){
stack.push(node.left);
}
}
return result;
}
}
4.中序遍历
中序遍历的顺序是左中右，即先左子树、根节点、右子树，那么我们先考虑递归进行求解。
思路和上面一样，唯一的区别就是变了顺序，所以总体的递归代码如下：
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<Integer>();
preorder(root, result);
return result;
}
public void preorder(TreeNode root, List<Integer> result) {
if (root == null) {
return;
}
preorder(root.left, result);
result.add(root.val); //注意
preorder(root.right, result);
}
}
对于迭代法，难度会更大一点！！！
中序遍历是左中右，但是代码和上面有一些不同，中序遍历是左中右，先访问的是二叉树顶部的节点，然后一层一层向下访问，直到到达树左面的最底部，再开始处理节点（也就是在把节点的数值放进result数组中），这就造成了处理顺序和访问顺序是不一致的。在使用迭代法写中序遍历，就需要借用指针的遍历来帮助访问节点，栈则用来处理节点上的元素。
所以我们可以写出代码如下：
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null){
return result;
}
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while (cur != null || !stack.isEmpty()){
if (cur != null){
stack.push(cur);
cur = cur.left;
}else{
cur = stack.pop();
result.add(cur.val);
cur = cur.right;
}
}
return result;
}
}
5.后序遍历
后序遍历的顺序是左右中，即先左子树、右子树、根节点，那么我们先考虑递归进行求解。
思路和上面一样，唯一的区别就是变了顺序，所以总体的递归代码如下：
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<Integer>();
preorder(root, result);
return result;
}
public void preorder(TreeNode root, List<Integer> result) {
if (root == null) {
return;
}
preorder(root.left, result);
preorder(root.right, result);
result.add(root.val); //注意
}
}
对于迭代法，会前序遍历难度会小一点！！！
先序遍历是中左右，后续遍历是左右中，那么我们只需要调整一下先序遍历的代码顺序，就变成中右左的遍历顺序，然后在反转result数组，输出的结果顺序就是左右中了，如下图：
所以我们可以很快的写出代码如下：
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null){
return result;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()){
TreeNode node = stack.pop();
result.add(node.val);
if (node.left != null){
stack.push(node.left);
}
if (node.right != null){
stack.push(node.right);
}
}
Collections.reverse(result);
return result;
}
}
注意，这里主要是入栈顺序变了，变成先左后右！！！
6.层序遍历
层序遍历一个二叉树。就是从左到右一层一层的去遍历二叉树。这种遍历的方式和我们之前讲过的都不太一样。
需要借用一个辅助数据结构即队列来实现，队列先进先出，符合一层一层遍历的逻辑，而是用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。
了解了思路，我们可以很快的写出层序遍历的代码：
class Solution {
public List<List<Integer>> resList = new ArrayList<List<Integer>>();
public List<List<Integer>> levelOrder(TreeNode root) {
checkFun02(root);
return resList;
}
public void checkFun02(TreeNode node) {
if (node == null) return;
Queue<TreeNode> que = new LinkedList<TreeNode>();
que.offer(node);
while (!que.isEmpty()) {
List<Integer> itemList = new ArrayList<Integer>();
int len = que.size();
while (len > 0) {
TreeNode tmpNode = que.poll();
itemList.add(tmpNode.val);
if (tmpNode.left != null) que.offer(tmpNode.left);
if (tmpNode.right != null) que.offer(tmpNode.right);
len--;
}
resList.add(itemList);
}
}
}
主要就是建立一个队列，依次对出队列的数的左右子树入队，同时记录下当前队列的大小，这样可以每一次得到一层的数。
怎么样，看完以后是不是简单多了，当然得有一点点这个方面基础，不然看起来还是有点费劲！！！
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK