Java：树的前序、中序、后序遍历代码实现--利用栈实现

刺骨的言语ヽ痛彻心扉 2024-03-23 12:15 4阅读 0赞

#### Java：树的前序、中序、后序遍历代码实现--利用栈实现 ####

*  前言
 *  一、具体实现代码
 *   *  1.前序遍历
     *  2.中序遍历
     *  3.后序遍历

--------------------

## 前言 ##

树的前序、中序、后序遍历是常见的树检索方式，本文分享了Java实现树的前序、中序、后序遍历的代码–利用栈实现

希望对大家有用！

--------------------

## 一、具体实现代码 ##

### 1.前序遍历 ###

import java.util.*;
    
    /*
     * public class TreeNode {
     *   int val = 0;
     *   TreeNode left = null;
     *   TreeNode right = null;
     *   public TreeNode(int val) {
     *     this.val = val;
     *   }
     * }
     */
    
    public class Solution {
        
        /**
         * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
         *
         * 
         * @param root TreeNode类 
         * @return int整型一维数组
         */
        public int[] preorderTraversal (TreeNode root) {
        
            // write code here
            List<Integer> list=new ArrayList<>();
            Stack<TreeNode> s = new Stack<TreeNode>();
            if(root == null)
                return  new int[0];
            s.push(root);
            while(!s.isEmpty()){
        
                TreeNode node=s.pop();
                list.add(node.val);
                if(node.right!=null){
        
                    s.push(node.right);
                }
                if(node.left!=null){
        
                    s.push(node.left);
                }
            }
            int[] res = new int[list.size()];
            for(int i=0;i<list.size();i++){
        
                res[i]=list.get(i);
            }
            return res;
        }
    }

### 2.中序遍历 ###

import java.util.*;
    
    /*
     * public class TreeNode {
     *   int val = 0;
     *   TreeNode left = null;
     *   TreeNode right = null;
     *   public TreeNode(int val) {
     *     this.val = val;
     *   }
     * }
     */
    
    public class Solution {
        
        public int[] inorderTraversal (TreeNode root) {
        
            //添加遍历结果的数组
            List<Integer> list = new ArrayList();
            Stack<TreeNode> s = new Stack<TreeNode>();
            //空树返回空数组
            if(root == null)
                return new int[0];
            //当树节点不为空或栈中有节点时
            while(root != null || !s.isEmpty()){
        
                //每次找到最左节点
                while(root != null){
        
                    s.push(root);
                    root = root.left;
                }
                //访问该节点
                TreeNode node = s.pop();
                list.add(node.val);
                //进入右节点
                root = node.right;
            }
            //返回的结果
            int[] res = new int[list.size()];
            for(int i = 0; i < list.size(); i++)
                res[i] = list.get(i);
            return res;
        }
    }

### 3.后序遍历 ###

import java.util.*;
    
    /*
     * public class TreeNode {
     *   int val = 0;
     *   TreeNode left = null;
     *   TreeNode right = null;
     *   public TreeNode(int val) {
     *     this.val = val;
     *   }
     * }
     */
    
    public class Solution {
        
        public int[] postorderTraversal (TreeNode root) {
        
            //添加遍历结果的数组
            List<Integer> list = new ArrayList();
            Stack<TreeNode> s = new Stack<TreeNode>();
            TreeNode pre = null;
            while(root != null || !s.isEmpty()){
        
                //每次先找到最左边的节点
                while(root != null){
        
                    s.push(root);
                    root = root.left;
                }
                //弹出栈顶
                TreeNode node = s.pop();
                //如果该元素的右边没有或是已经访问过
                if(node.right == null || node.right == pre){
        
                    //访问中间的节点
                    list.add(node.val);
                    //且记录为访问过了
                    pre = node;
                }else{
        
                    //该节点入栈
                    s.push(node);
                    //先访问右边
                    root = node.right;
                }
            }
            //返回的结果
            int[] res = new int[list.size()];
            for(int i = 0; i < list.size(); i++)
                res[i] = list.get(i);
            return res;
        }
    }

更多内容可以参考：[BM23 二叉树的前序遍历][BM23]

[BM23]: https://www.nowcoder.com/practice/5e2135f4d2b14eb8a5b06fab4c938635