总结Java实现二叉树的各种遍历

偏执的太偏执、 2023-01-02 03:20 131阅读 0赞

### 文章目录 ###

*  一. 问题背景
 *  二. 遍历二叉树的算法
 *   *  2.1 用递归解决
     *   *  2.1.1 概念
         *  2.1.2 代码
     *  2.2 用层次遍历解决
     *   *  2.2.1 概念
         *  2.2.2 代码
     *  2.3 用深度遍历解决
     *   *  2.3.1 概念
         *  2.3.2 代码

# 一. 问题背景 #

刷牛客《剑指offer》的时候，关于树的遍历算法，大概有两个解法：递归；层次遍历（广度优先）；深度遍历（深度优先）。今天做个小总结。

源码：[前往gitee页面下载][gitee]，详细介绍见readme.md文件

# 二. 遍历二叉树的算法 #

以下所有测试用例使用的二叉树如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNjM0ODQ2_size_16_color_FFFFFF_t_70_pic_center]

## 2.1 用递归解决 ##

### 2.1.1 概念 ###

**递归解法主要是三种遍历顺序：先序遍历（根、左子树、右子树）；中序遍历（左子树、根、右子树）；后序遍历（左子树、右子树、根）。这个序指的是根节点的序，先遍历根节点则是先序遍历根节点，中序遍历指的是在中间才遍历根节点，后序遍历指的是最后才遍历根节点。**

### 2.1.2 代码 ###

package com.androidla.buildtree;
    
    import lombok.extern.slf4j.Slf4j;
    import org.junit.Test;
    
    import java.util.ArrayList;
    import java.util.List;
    
    /** * @Author Androidla * @Date 2021/1/4 14:35 * @Description 遍历二叉树的算法 **/
    @Slf4j
    public class TraverseBinaryTree { 
    
        List<Integer> preOrderList = new ArrayList<>();
        List<Integer> inOrderList = new ArrayList<>();
        List<Integer> afterOrderList = new ArrayList<>();
    
        // 二叉树的节点
        private static class TreeNode { 
            int val = 0;
            TreeNode left = null;
            TreeNode right = null;
    
            TreeNode(int val, TreeNode left, TreeNode right) { 
                this.val = val;
                this.left = left;
                this.right = right;
            }
    
            TreeNode(int val) { 
                this.val = val;
            }
        }
    
        /** * 前序遍历 * @param node * @return */
        public List<Integer> preOrderTraverse(TreeNode node) { 
            if (node == null) { 
                return preOrderList;
            }
            preOrderList.add(node.val);
            preOrderTraverse(node.left);
            preOrderTraverse(node.right);
            return preOrderList;
        }
    
        /** * 中序遍历 * @param node * @return */
        public List<Integer> inOrderTraverse(TreeNode node) { 
            if (node == null) { 
                return inOrderList;
            }
            inOrderTraverse(node.left);
            inOrderList.add(node.val);
            inOrderTraverse(node.right);
            return inOrderList;
        }
    
        /** * 后序遍历 * @param node * @return */
        public List<Integer> afterOrderTraverse(TreeNode node) { 
            if (node == null) { 
                return afterOrderList;
            }
            afterOrderTraverse(node.left);
            afterOrderTraverse(node.right);
            afterOrderList.add(node.val);
            return afterOrderList;
        }
    
        @Test
        public void test() { 
            TreeNode node1 = new TreeNode(1, null, null);
            TreeNode node2 = new TreeNode(2, null, null);
            TreeNode node3 = new TreeNode(3, null, null);
            TreeNode node4 = new TreeNode(4, null, null);
            TreeNode node5 = new TreeNode(5, node4, node3);
            TreeNode node6 = new TreeNode(6, node2, node1);
            TreeNode node7 = new TreeNode(7, node6, node5);
            List<Integer> preOrder = preOrderTraverse(node7);
            List<Integer> inOrder = inOrderTraverse(node7);
            List<Integer> afterOrder = afterOrderTraverse(node7);
            log.info("preOrderList is: {}", preOrder);
            log.info("inOrderList is : {}", inOrder);
            log.info("afterOrderList is: {}", afterOrder);
        }
    
    }

## 2.2 用层次遍历解决 ##

### 2.2.1 概念 ###

**层次遍历，按层来遍历二叉树的每一层。层次遍历可以用队列或者动态数组（即ArrayList动态数组）来完成。用队列来存储每一个层的所有节点。个人喜欢用LinkedList来实现（LinkedList有实现队列接口）。刷算法题的时候根据具体情况选择，有时候ArrayList和LinkedList要一起配合使用。**

### 2.2.2 代码 ###

**这里列出核心代码，其余省略无用的代码可以从前面递归遍历的代码中找到**

/** * 层次遍历二叉树 * @param node * @return 返回的格式为[[], [], []] */
        public List<ArrayList<Integer>> levelTraverse(TreeNode node) { 
            List<ArrayList<Integer>> result = new ArrayList<>();
            Queue<TreeNode> queue = new LinkedList<>();
    
            if (node == null) { 
                return new ArrayList<>();
            }
    
            // 加入队列
            queue.offer(node);
    
            while (!queue.isEmpty()) { 
                // 返回结果的格式弄成[[], [], []]，因此要获取size
                int size = queue.size();
                ArrayList<Integer> list = new ArrayList<>();
                for (int i = 0; i < size; i++) { 
                    // 出队列
                    TreeNode curNode = queue.poll();
                    if (curNode == null) continue;
    
                    // 入队
                    if (curNode.left != null) queue.offer(curNode.left);
                    if (curNode.right != null) queue.offer(curNode.right);
    
                    list.add(curNode.val);
                }
                result.add(list);
            }
    
            return result;
        }
    
    	/** * 测试层次遍历 */
        @Test
        public void testlevelTraverse() { 
            TreeNode node1 = new TreeNode(1, null, null);
            TreeNode node2 = new TreeNode(2, null, null);
            TreeNode node3 = new TreeNode(3, null, null);
            TreeNode node4 = new TreeNode(4, null, null);
            TreeNode node5 = new TreeNode(5, node4, node3);
            TreeNode node6 = new TreeNode(6, node2, node1);
            TreeNode node7 = new TreeNode(7, node6, node5);
            List<ArrayList<Integer>> result = levelTraverse(node7);
            log.info("result is: {}", result);
        }

## 2.3 用深度遍历解决 ##

### 2.3.1 概念 ###

**深度优先遍历用递归解决其实就是先序、中序、后序的递归思想。非递归可以用栈来实现（要注意先压入左节点，最终是左节点后出来）。**

### 2.3.2 代码 ###

/** * 深度优先遍历 * @param node * @return */
        public Stack<Integer> depthTraverse(TreeNode node) { 
            if (node == null) { 
                return new Stack<>();
            }
    
            Stack<Integer> result = new Stack<>();
            Stack<TreeNode> stack = new Stack<>();
    
            stack.push(node);
    
            while (!stack.isEmpty()) { 
                TreeNode curNode = stack.pop();
    
                if (curNode == null) continue;
    
                // 先遍历树的左边，后遍历树的右边，栈是先进后出
                if (curNode.right != null) stack.push(curNode.right);
                if (curNode.left != null) stack.push(curNode.left);
    
                result.push(curNode.val);
            }
    
            return result;
        }
    
    	/** * 测试深度遍历 */
        @Test
        public void testDepthTraverse() { 
            TreeNode node1 = new TreeNode(1, null, null);
            TreeNode node2 = new TreeNode(2, null, null);
            TreeNode node3 = new TreeNode(3, null, null);
            TreeNode node4 = new TreeNode(4, null, null);
            TreeNode node5 = new TreeNode(5, node4, node3);
            TreeNode node6 = new TreeNode(6, node2, node1);
            TreeNode node7 = new TreeNode(7, node6, node5);
            Stack<Integer> result = depthTraverse(node7);
    
            while (!result.isEmpty()) { 
                Integer value = result.pop();
                log.info("{}", value);
            }
            log.info("result is: {}", result);
        }

[gitee]: https://gitee.com/zilianggan/build-tree
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNjM0ODQ2_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/c1a6acafdc6a4420b722d25641306f35.png