二叉树的遍历 java版

桃扇骨 2022-05-14 08:48 93阅读 0赞

总结二叉树的前序、中序、后序遍历，包含递归与非递归方式，以及层次遍历，递归方式比较简单，非递归前中后序主要使用一个辅助栈，层次遍历主要使用一个辅助队列。代码如下：

import java.util.ArrayList;
    import java.util.LinkedList;
    import java.util.List;
    
    /**
     * Created by yhu on 2018/9/5.
     */
    public class 二叉树遍历总结 {
        /**
         * 前序递归
         * @param root
         * @return
         */
        public static List<Integer> preOrder1(TreeNode root) {
            ArrayList<Integer> list = new ArrayList<>();
            if (null == root) {
                return list;
            }
            list.add(root.val);
            list.addAll(preOrder1(root.left));
            list.addAll(preOrder1(root.right));
            return list;
        }
    
        /**
         * 中序递归
         * @param root
         * @return
         */
        public static List<Integer> inOrder1(TreeNode root) {
            ArrayList<Integer> list = new ArrayList<>();
            if (null == root) {
                return list;
            }
            list.addAll(inOrder1(root.left));
            list.add(root.val);
            list.addAll(inOrder1(root.right));
            return list;
        }
    
        /**
         * 后续递归
         * @param root
         * @return
         */
        public static List<Integer> postOrder1(TreeNode root) {
            ArrayList<Integer> list = new ArrayList<>();
            if (null == root) {
                return list;
            }
            list.addAll(postOrder1(root.left));
            list.addAll(postOrder1(root.right));
            list.add(root.val);
            return list;
        }
    
        /**
         * 前序非递归
         * @param root
         * @return
         */
        public static List<Integer> preOrder2(TreeNode root) {
            ArrayList<Integer> list = new ArrayList<>();
            TreeNode cur = root;
            LinkedList<TreeNode> stack = new LinkedList<>();
            if (null == root) {
                return list;
            }
            while (cur != null || !stack.isEmpty()) {
                if (cur != null) {
                    list.add(cur.val);
                    stack.push(cur);
                    cur = cur.left;
                } else {
                    cur = stack.pop().right;
                }
            }
            return list;
        }
    
        /**
         * 中序非递归
         * @param root
         * @return
         */
        public static List<Integer> inOrder2(TreeNode root) {
            ArrayList<Integer> list = new ArrayList<>();
            TreeNode cur = root;
            LinkedList<TreeNode> stack = new LinkedList<>();
            if (null == root) {
                return list;
            }
            while (cur != null || !stack.isEmpty()) {
                if (cur != null) {
                    stack.push(cur);
                    cur = cur.left;
                } else {
                    list.add(stack.peek().val);  //已添加
                    cur = stack.pop().right;   //左，根已完成，看右
                }
            }
            return list;
        }
    
        /**
         * 后序非递归
         * @param root
         * @return
         */
        public static List<Integer> postOrder2(TreeNode root) {
            ArrayList<Integer> list = new ArrayList<>();
            TreeNode cur = root;
            TreeNode preV = null;  //区分左子树还是右子树
            LinkedList<TreeNode> stack = new LinkedList<>();
            if (null == root) {
                return list;
            }
            while (cur != null || !stack.isEmpty()) {
                if (cur != null) {
                    stack.push(cur);
                    cur = cur.left;
                } else {
                    cur = stack.peek().right;
                    if (cur != null && cur != preV) {
                        stack.push(cur);
                        cur = cur.left;
                    } else {
                        preV = stack.pop();
                        list.add(preV.val);
                        cur = null;
                    }
                }
            }
            return list;
        }
    
        /**
         * 层次遍历
         * @param root
         * @return
         */
        public static List<Integer> levelOrder(TreeNode root) {
            ArrayList<Integer> list = new ArrayList<>();
            if (null == root) {
                return list;
            }
            LinkedList<TreeNode> queue = new LinkedList<>();
            queue.add(root);
            while (!queue.isEmpty()) {
                TreeNode node = queue.poll();  //从队首获取元素，同时获取的这个元素将从原队列删除
                list.add(node.val);
                if (node.left != null) {
                    queue.addLast(node.left);
                }
                if (node.right != null) {
                    queue.addLast(node.right);
                }
            }
            return list;
        }
    
        public static void main(String[] args){
            TreeNode root = new TreeNode(1);
            root.left = new TreeNode(4);
            root.right = new TreeNode(2);
            root.right.left = new TreeNode(3);
            List<Integer> list_preOrder1 = preOrder1(root);
            System.out.print("前序递归: "+'\t');
            System.out.println(list_preOrder1.toString());
    
            List<Integer> list_inOrder1 = inOrder1(root);
            System.out.print("中序递归: "+'\t');
            System.out.println(list_inOrder1.toString());
    
            List<Integer> list_postOrder1 = postOrder1(root);
            System.out.print("后序递归: "+'\t');
            System.out.println(list_postOrder1.toString());
            System.out.println();
    
    
            List<Integer> list_preOrder2 = preOrder2(root);
            System.out.print("前序非递归: "+'\t');
            System.out.println(list_preOrder2.toString());
    
            List<Integer> list_inOrder2 = inOrder2(root);
            System.out.print("中序非递归: "+'\t');
            System.out.println(list_inOrder2.toString());
    
            List<Integer> list_postOrder2 = postOrder2(root);
            System.out.print("后序非递归: "+'\t');
            System.out.println(list_postOrder2.toString());
            System.out.println();
    
            List<Integer> list_levelOrder = levelOrder(root);
            System.out.print("层次遍历: "+'\t');
            System.out.println(list_levelOrder.toString());
        }
    }