二叉树前中后序遍历的递归和非递归实现

古城微笑少年丶 2022-11-14 10:07 164阅读 0赞

### 目录 ###

*  二叉树遍历
 *  前序遍历
 *   *  递归
     *  非递归
 *  中序遍历
 *   *  递归
     *  非递归
 *  后序遍历
 *   *  递归
     *  非递归

# 二叉树遍历 #

二叉树的遍历分为深度优先和广度优先  
深度优先又分为前序遍历、中序遍历和后序遍历  
详见：[初识二叉树][Link 1]

我们可以理解为对结点的处理顺序在前、中间还是最后  
例如：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70]

# 前序遍历 #

[二叉树的前序遍历][Link 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 1]

## 递归 ##

public List<Integer> preorderTraversal(TreeNode root) { 
            List<Integer> list = new ArrayList<>();
               if(root == null){ 
                return list;
            }
            list.add(root.val);
            List<Integer> left = preorderTraversal(root.left);
            List<Integer> right =preorderTraversal(root.right);
            list.addAll(left);
            list.addAll(right);
            return list;
        }

## 非递归 ##

思路：  
我们提前准备一个栈，保存所经过的路径，然后从根节点一直向左出发，当左孩子为空，然后找右孩子，然后回溯，直到找完。

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

# 中序遍历 #

[二叉树的中序遍历][Link 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 2]

## 递归 ##

public List<Integer> inorderTraversal(TreeNode root) { 
            List<Integer> list = new ArrayList<>();
            if (root == null) { 
                return list;
            }
            List<Integer> left = inorderTraversal(root.left);
            list.addAll(left);
            list.add(root.val);
            List<Integer> right = inorderTraversal(root.right);
            list.addAll(right);
    
            return list;
        }

## 非递归 ##

思路：  
我们提前准备一个栈，保存所经过的路径，然后从根节点一直向左出发，当左孩子为空，然后找右孩子，然后回溯，直到找完。

public List<Integer> inorderTraversal(TreeNode root) { 
            List<Integer> list = new ArrayList<>();
            if (root == null) { 
                return list;
            }
    
            Stack<TreeNode> stack = new Stack<>();
            TreeNode cur = root;
            while (cur != null || !stack.isEmpty()) { 
                while (cur != null) { 
                    stack.push(cur);
                    cur = cur.left;
                }
                TreeNode node = stack.pop();
                list.add(node.val);
                cur = node.right;
            }
            return list;
        }

# 后序遍历 #

[二叉树的后序遍历][Link 4]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 3]

## 递归 ##

public List<Integer> postorderTraversal1(TreeNode root) { 
            List<Integer> list = new ArrayList<>();
            if (root == null) { 
                return list;
            }
    
            List<Integer> left = postorderTraversal(root.left);
            list.addAll(left);
            List<Integer> right = postorderTraversal(root.right);
            list.addAll(right);
            list.add(root.val);
    
            return list;
        }

## 非递归 ##

思路：  
相比之下，后序遍历的非递归比前两个要麻烦一点，因为不是简单的删除栈顶元素，如果处理不好会造成死循环，所以我们需要判断右孩子是否为空，和是否刚走过右孩子。

public List<Integer> postorderTraversal(TreeNode root) { 
            List<Integer> list = new ArrayList<>();
            if (root == null) { 
                return list;
            }
    
            Stack<TreeNode> stack = new Stack<>();
            TreeNode cur = root;
            TreeNode last = null;
    
            while (cur != null || !stack.isEmpty()) { 
                while (cur != null) { 
                    stack.push(cur);
                    cur = cur.left;
                }
    
                TreeNode node = stack.peek();
    
                if (node.right == null || node.right == last) { 
                    // 看作第三次经过
                    list.add(node.val);
                    last = node;
                    stack.pop();
                } else { 
                    // 第二次经过
                    cur = node.right;
                }
            }
            return list;
        }

[Link 1]: https://blog.csdn.net/weixin_52142731/article/details/115220279
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70]: /images/20221022/78068d9ac0634a23903335769a7f1626.png
[Link 2]: https://leetcode-cn.com/problems/binary-tree-preorder-traversal/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 1]: /images/20221022/b4acd938fac7473fae91f15aca122270.png
[Link 3]: https://leetcode-cn.com/problems/binary-tree-inorder-traversal/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 2]: /images/20221022/e88fd81a8883411984d74dfed0178b47.png
[Link 4]: https://leetcode-cn.com/problems/binary-tree-postorder-traversal/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 3]: /images/20221022/df10cde1384c4f7b8b5f011fdca2d8cd.png