二叉树的几种遍历方式（附 LeetCode 水题）

正文之前

闲得无聊去刷 LeetCode 的时候做了一点深搜和广搜的题，但是树的遍历方式还没有写过总结，今天刚好总结一下：

1. 深度优先搜索
   • 前序遍历
   • 中序遍历
   • 后序遍历
2. 广度优先搜索

正文

1. 节点的定义

这里定义树的节点的方式就按照 LeetCode 上给出的吧：

class TreeNode {
     int val;
     TreeNode left;
     TreeNode right;
     TreeNode(int x) { val = x; }
}

接下来给出用例：

        TreeNode node10 = new TreeNode(10);
        TreeNode node7 = new TreeNode(7);
        TreeNode node8 = new TreeNode(8);
        TreeNode node1 = new TreeNode(1);
        TreeNode node3 = new TreeNode(3);
        TreeNode node0 = new TreeNode(0);
        TreeNode node2 = new TreeNode(2);
        TreeNode node4 = new TreeNode(4);
        TreeNode node6 = new TreeNode(6);
        node10.left = node7;
        node10.right = node8;
        node7.left = node1;
        node7.right = node3;
        node3.left = node0;
        node3.right = node2;
        node8.left = node4;
        node8.right = node6;

在遍历时用 ArrayList 来存放根节点的值，

2. 深度优先搜索

分别有三种方式，前序先访问根节点，中序第二个访问根节点，后序最后访问根节点，这里写给出三种方法，然后统一测试一下：

    //前序遍历
    public void preOrderTraversal(TreeNode node, ArrayList<Integer> list){
        if (node == null){
            return;
        }
        //先访问根节点
        list.add(node.val);
        //然后是左子节点和右子节点
        preOrderTraversal(node.left, list);
        preOrderTraversal(node.right, list);
    }

    //中序遍历
    public void inOrderTraversal(TreeNode node, ArrayList<Integer> list){
        if (node == null){
            return;
        }
        //先访问左子节点，然后是根节点，最后是右子节点
        inOrderTraversal(node.left, list);
        list.add(node.val);
        inOrderTraversal(node.right, list);
    }

    //后序遍历
    public void postOrderTraversal(TreeNode node, ArrayList<Integer> list){
        if (node == null){
            return;
        }
        postOrderTraversal(node.left, list);
        postOrderTraversal(node.right, list);
        list.add(node.val);
    }

根据我们定义的用例，三种遍历方式的输出分别是这样的：

        ArrayList<Integer> list = new ArrayList<>();

        System.out.print("前序遍历：");
        s.preOrderTraversal(node10, list);
        for (Integer i: list) {
            System.out.print(i + " ");
        }
        list.clear();
        System.out.println();

        System.out.print("中序遍历：");
        s.inOrderTraversal(node10, list);
        for (Integer i: list) {
            System.out.print(i + " ");
        }
        list.clear();
        System.out.println();

        System.out.print("后序遍历：");
        s.postOrderTraversal(node10, list);
        for (Integer i: list) {
            System.out.print(i + " ");
        }

得到输出：

前序遍历：10 7 1 3 0 2 8 4 6
中序遍历：1 7 0 3 2 10 4 8 6
后序遍历：1 0 2 3 7 4 6 8 10

3. 广度优先搜索

广搜的方式就是一层一层的访问节点，又叫做层次遍历，用队列来实现：

    public void BFS(TreeNode node, ArrayList<Integer> list){
        Queue<TreeNode> queue = new LinkedList<>();
        if (node != null){
            //根节点作为第一层，先加入
            queue.add(node);
            while (!queue.isEmpty()){
                TreeNode cur = queue.poll();
                list.add(cur.val);
                //依次加入左右子节点
                if (cur.left != null){
                    queue.offer(cur.left);
                }
                if (cur.right != null){
                    queue.offer(cur.right);
                }
            }
        }
    }

遍历的结果是：

层次遍历：10 7 8 1 3 4 6 0 2 

我用图来走一遍流程：

每次出队列一个节点，然后把它的子节点（如果存在）加入到队列，循环往复，直到队列为空

4. LeetCode 水题

既然介绍了树的遍历，就随便拿两个简单的题来做个例子吧：

257. Binary Tree Paths

求二叉树的所有路径，这一题可能和遍历有一点区别（因为是路径，根节点会出现多次），不过想法是一样的，用的前序，先访问根节点，然后是左右子节点：

    public List<String> binaryTreePaths(TreeNode root) {
        String s = "";
        List<String> list = new ArrayList<>();
        if (root != null){
            DFS(s, root, list);
        }
        
        return list;
        
    }
    public void DFS(String s, TreeNode node, List<String> list){
        if (node.left == null && node.right == null){
            list.add(s + node.val);
        }
        if (node.left != null){
            DFS(s + node.val + "->", node.left, list);
        }
        if (node.right != null){
            DFS(s + node.val + "->", node.right, list);
        }
    }

513. Find Bottom Left Tree Value

求二叉树最底层的最左边节点，用的层次遍历，只不过这次是从右往左，最后一个出队列的就是目标节点了：

    public int findBottomLeftValue(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()){
            root = queue.poll();
            if (root.right != null){
                queue.add(root.right);
            }if (root.left != null){
                queue.add(root.left);
            }
        }
        return root.val;
    }

关于树的遍历就到这里了