数据结构:二叉树的非递归遍历

野性酷女 2023-09-28 15:54 191阅读 0赞

####  ####

*  二叉树的前序遍历
 *   *  题目描述
     *  思路
     *  代码
 *  二叉树的中序遍历
 *   *  题目描述
     *  思路
     *  代码
 *  二叉树的后序遍历
 *   *  题目描述
     *  思路
     *  代码
 *  二叉树的层序遍历
 *   *  题目描述
     *  前提知识
     *  代码

## 二叉树的前序遍历 ##

[144.二叉树的前序遍历][144.]

### 题目描述 ###

给你二叉树的根节点 root ，返回它节点值的 前序 遍历。  
![在这里插入图片描述][5e82429435ef41a6937dd68443250466.png]  
提示：

树中节点数目在范围 \[0, 100\] 内  
\-100 <= Node.val <= 100

### 思路 ###

我们知道前序遍历是按照**根–>左子树–>右子树**的顺序来遍历的，如果要使用迭代的方法来解决，我们可以使用栈来解决，先把根节点放入栈中，然后将右孩子加入栈，再加入左孩子。因为这样子进栈后，出栈的顺序就是**根–>左子树–>右子树**

![在这里插入图片描述][fbd72981dbec4ff583f87408f400a319.png]

### 代码 ###

class Solution {
        
        public List<Integer> preorderTraversal(TreeNode root) {
        
            List<Integer> list=new ArrayList();
            Stack<TreeNode> stack=new Stack();
            if(root==null){
        
                return list;
            }
            //只要栈非空，则把栈顶元素弹出
            stack.push(root);
            while(!stack.isEmpty()){
        
                TreeNode node= stack.pop();
                list.add(node.val);
                if(node.right!=null){
        
                     stack.push(node.right);
                }
                if(node.left!=null){
        
                     stack.push(node.left);
                }
               
               
            }
            return list;
    
        }
    }

## 二叉树的中序遍历 ##

### 题目描述 ###

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。  
![在这里插入图片描述][ba4608212f1648be97e46835b2b40307.png]  
提示：

树中节点数目在范围 \[0, 100\] 内  
\-100 <= Node.val <= 100

### 思路 ###

中序遍历是左中右，先访问的是二叉树顶部的节点，然后一层一层向下访问，直到到达树左面的最底部，再开始处理节点（也就是在把节点的数值放进result数组中）  
那么在使用迭代法写中序遍历，就需要借用指针的遍历来帮助访问节点，栈则用来处理节点上的元素。  
![在这里插入图片描述][f6916e956cc547cda9d272cadd8fd2c4.png]

### 代码 ###

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;
    	}
    }

## 二叉树的后序遍历 ##

[后序遍历][Link 1]

### 题目描述 ###

给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。  
![在这里插入图片描述][f4e05121a5494311b62cc49328773cf2.png]  
提示：

树中节点的数目在范围 \[0, 100\] 内  
\-100 <= Node.val <= 100

### 思路 ###

后续遍历的遍历顺序是左右根，前序遍历的遍历顺序是根左右，我们发现我们只需要调整一下左右孩子的进栈顺序，然后再反转一下，就可以得到后序遍历  
![在这里插入图片描述][f6fed5b74edc4dd483ee5619354c9133.png]

### 代码 ###

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

## 二叉树的层序遍历 ##

[层序遍历][Link 2]

### 题目描述 ###

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。  
![在这里插入图片描述][939d6d67a7f346b7b405d548b7c340fb.png]

### 前提知识 ###

在解决这道题目之前，我们应该先了解什么是层序遍历  
**层序遍历一个二叉树。就是从左到右一层一层的去遍历二叉树。**  
**队列先进先出，符合一层一层遍历的逻辑，我们可以使用队列来实现层序遍历**  
![在这里插入图片描述][c23d9e6e93624546a62c1f59fd673e84.png]

public void levelOrderTraversal(Node root){
        
        if(root==null){
        
            return;
        }
        Queue<Node> queue=new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
        
            Node node=queue.poll();
            System.out.print(node.val+" ");
            if(node.left!=null) {
        
                queue.offer(node.left);
            }
            if(node.right!=null) {
        
                queue.offer(node.right);
            }
        }
    }

### 代码 ###

class Solution {
        
    	public List<List<Integer>> levelOrder(TreeNode root) {
        
    		if(root==null) {
        
    			return new ArrayList<List<Integer>>();
    		}
    		
    		List<List<Integer>> res = new ArrayList<List<Integer>>();
    		Queue<TreeNode> queue = new LinkedList<TreeNode>();
    		//将根节点放入队列中，然后不断遍历队列
    		queue.add(root);
    		while(queue.size()>0) {
        
    			//获取当前队列的长度，这个长度相当于 当前这一层的节点个数
    			int size = queue.size();
    			ArrayList<Integer> tmp = new ArrayList<Integer>();
    			//将队列中的元素都拿出来(也就是获取这一层的节点)，放到临时list中
    			//如果节点的左/右子树不为空，也放入队列中
    			for(int i=0;i<size;++i) {
        
    				TreeNode t = queue.poll();
    				tmp.add(t.val);
    				if(t.left!=null) {
        
    					queue.offer(t.left);
    				}
    				if(t.right!=null) {
        
    					queue.offer(t.right);
    				}
    			}
    			//将临时list加入最终返回结果中
    			res.add(tmp);
    		}
    		return res;
    	}
    }

[144.]: https://leetcode.cn/problems/binary-tree-preorder-traversal/
[5e82429435ef41a6937dd68443250466.png]: https://img-blog.csdnimg.cn/5e82429435ef41a6937dd68443250466.png
[fbd72981dbec4ff583f87408f400a319.png]: https://img-blog.csdnimg.cn/fbd72981dbec4ff583f87408f400a319.png
[ba4608212f1648be97e46835b2b40307.png]: https://img-blog.csdnimg.cn/ba4608212f1648be97e46835b2b40307.png
[f6916e956cc547cda9d272cadd8fd2c4.png]: https://img-blog.csdnimg.cn/f6916e956cc547cda9d272cadd8fd2c4.png
[Link 1]: https://leetcode.cn/problems/binary-tree-postorder-traversal/
[f4e05121a5494311b62cc49328773cf2.png]: https://img-blog.csdnimg.cn/f4e05121a5494311b62cc49328773cf2.png
[f6fed5b74edc4dd483ee5619354c9133.png]: https://img-blog.csdnimg.cn/f6fed5b74edc4dd483ee5619354c9133.png
[Link 2]: https://leetcode.cn/problems/binary-tree-level-order-traversal/
[939d6d67a7f346b7b405d548b7c340fb.png]: https://img-blog.csdnimg.cn/939d6d67a7f346b7b405d548b7c340fb.png
[c23d9e6e93624546a62c1f59fd673e84.png]: https://img-blog.csdnimg.cn/c23d9e6e93624546a62c1f59fd673e84.png