二叉树前中后序遍历

r囧r小猫 2024-03-27 15:00 65阅读 0赞

> [牛客华为机试题库【题号 HJ开头】（重点看）][HJ]  
> [牛客在线编程算法篇【题号NC开头】][NC]  
> [剑指offer【题号 JZ开头】][offer_ JZ]  
> [力扣][Link 1]

### 1）原题链接 ###

[【leetcode】144. 二叉树的前序遍历][leetcode_144.]  
[【leetcode】194. 二叉树的中序遍历][leetcode_194.]  
[【leetcode】145. 二叉树的后序遍历][leetcode_145.]

### 2）已有题解 ###

### 3）代码 ###

#### 3.1、前期准备 ####

/**
         * 创建一棵二叉树
         *
         * @return 根节点
         */
        public static BinTreeNode<Character> createBinTree() {
        
            BinTreeNode<Character> RR2 = new BinTreeNode<>('F', null, null);
            BinTreeNode<Character> LR2 = new BinTreeNode<>('E', null, null);
            BinTreeNode<Character> LL2 = new BinTreeNode<>('D', null, null);
            BinTreeNode<Character> L1 = new BinTreeNode<>('B', LL2, LR2);
            BinTreeNode<Character> R1 = new BinTreeNode<>('C', null, RR2);
            BinTreeNode<Character> node = new BinTreeNode<>('A', L1, R1);
            return node;
        }
    
        /**
         * 前序递归法
         */
        public static void preOrderRecursion(BinTreeNode<Character> root, List<Character> res) {
        
            if (root == null) {
        
                return;
            }
            res.add(root.data);
            preOrderRecursion(root.lchild, res);
            preOrderRecursion(root.rchild, res);
        }

#### 3.2、前序，中序，后序遍历(递归实现) ####

/**
         * 前序递归法
         */
        public static void preOrderRecursion(BinTreeNode<Character> root, List<Character> res) {
        
            if (root == null) {
        
                return;
            }
            res.add(root.data);
            preOrderRecursion(root.lchild, res);
            preOrderRecursion(root.rchild, res);
        }
    
        /**
         * 中序递归法
         */
        public static void inOrderRecursion(BinTreeNode<Character> root, List<Character> res) {
        
            if (root == null) {
        
                return;
            }
            inOrderRecursion(root.lchild, res);
            res.add(root.data);
            inOrderRecursion(root.rchild, res);
        }
    
        /**
         * 后序递归法
         */
        public static void postOrderRecursion(BinTreeNode<Character> root, List<Character> res) {
        
            if (root == null) {
        
                return;
            }
            postOrderRecursion(root.lchild, res);
            postOrderRecursion(root.rchild, res);
            res.add(root.data);
        }

#### 3.2、前序，中序，后序遍历(迭代实现) ####

/**
         * 前序遍历：迭代法
         */
        public static List<Character> preOrder(BinTreeNode<Character> root) {
        
    
            // 结果收集容器
            List<Character> res = new ArrayList<>();
    
            // Stack
            Deque<BinTreeNode<Character>> stack = new LinkedList<>();
            
            // root != null 表示当前节点是作为根节点进入的
            // root == null 表示当前节点得位置是作为右节点进来的
            // root != null是针对有值处理的场景、!stack.isEmpty()是针对root = null时的场景
            while (root != null || !stack.isEmpty()) {
        
                while (root != null) {
         // 子节点有值就先入Stack
                    res.add(root.data); // 前序遍历故遇到根节点就收集值
                    stack.push(root);
                    root = root.lchild; // 再看子节点的左子节点是否有值
                }
    
                root = stack.pop(); // 左弹根→右弹根父
                root = root.rchild; // 弹出父节点后取出其右子节点
            }
    
            return res;
        }
    
    
        /**
         * 中序迭代法
         */
        public static List<Character> inOrder(BinTreeNode<Character> root) {
        
            List<Character> res = new ArrayList<>();
    
            Deque<BinTreeNode<Character>> stack = new LinkedList<>();
    
            while (root != null || !stack.isEmpty()) {
        
                while (root != null) {
        
                    stack.push(root);
                    root = root.lchild;
                }
    
                root = stack.pop();
                res.add(root.data); // 左弹根→此时左子节点处理完毕弹出根节点，中序遍历故收集根节点值
                root = root.rchild;
            }
    
            return res;
        }
    
    
        /**
         * 后序迭代法
         */
        public static List<Character> postOrder(BinTreeNode<Character> root) {
        
            List<Character> res = new ArrayList<>();
    
            Deque<BinTreeNode<Character>> stack = new LinkedList<>();
    
            BinTreeNode<Character> previous = null;
    
            while (root != null || !stack.isEmpty()) {
        
                while (root != null) {
        
                    stack.push(root);
                    root = root.lchild;
                }
    
                root = stack.pop(); // 左弹根→右弹根→再弹根父
    
                if (root.rchild == null || root.rchild == previous) {
        
                    res.add(root.data); // 上面的while包含了左右两种子节点情况、故这里单独处理右节点
                    previous = root;
                    root = null; // 赋值为null是为了触发右弹根父
                } else {
        
                    stack.push(root); // 右子节点有值且没走过,pop出来的根节点二次入栈
                    root = root.rchild;
                }
            }
    
            return res;
        }

#### 3.4、测试验证 ####

System.out.println("前序遍历：");
            List<Character> res = new ArrayList<>();
            preOrderRecursion(createBinTree(), res);
            System.out.println(res.stream().map(String::valueOf).collect(Collectors.joining(",")));
            List<Character> characters = preOrder(createBinTree());
            System.out.println(characters.stream().map(String::valueOf).collect(Collectors.joining(",")));
    
    
            System.out.println("中序遍历:");
            List<Character> res2 = new ArrayList<>();
            inOrderRecursion(createBinTree(), res2);
            System.out.println(res2.stream().map(String::valueOf).collect(Collectors.joining(",")));
            List<Character> characters2 = inOrder(createBinTree());
            System.out.println(characters2.stream().map(String::valueOf).collect(Collectors.joining(",")));
    
    
            System.out.println("后序遍历:");
            List<Character> res3 = new ArrayList<>();
            postOrderRecursion(createBinTree(), res3);
            System.out.println(res3.stream().map(String::valueOf).collect(Collectors.joining(",")));
            List<Character> characters3 = postOrder(createBinTree());
            System.out.println(characters3.stream().map(String::valueOf).collect(Collectors.joining(",")));

前序遍历：
    A,B,D,E,C,F
    A,B,D,E,C,F
    
    中序遍历:
    D,B,E,A,C,F
    D,B,E,A,C,F
    
    后序遍历:
    D,E,B,F,C,A
    D,E,B,F,C,A

[HJ]: https://www.nowcoder.com/exam/oj/ta?tpId=37
[NC]: https://www.nowcoder.com/exam/oj
[offer_ JZ]: https://www.nowcoder.com/exam/oj/ta?page=1&tpId=13&type=13
[Link 1]: https://leetcode.cn/problemset/all/
[leetcode_144.]: https://leetcode.cn/problems/binary-tree-preorder-traversal/
[leetcode_194.]: https://leetcode.cn/problems/binary-tree-inorder-traversal/
[leetcode_145.]: https://leetcode.cn/problems/binary-tree-postorder-traversal/