vlambda博客
学习文章列表

二叉树是平时最常见的数据结构之一。

它属于树的一种，其中每个节点都不能有多余两个的儿子。

在面试或者平常做算法题时，如果遇到二叉树类的题目，基本都要借助到二叉树的遍历，下面就来介绍一下二叉树的几种常见遍历方式。

二叉树的遍历主要分为：深度优先遍历和广度优先遍历。

深度优先遍历

英文缩写为DFS即Depth First Search.其过程简要来说是对每一个可能的分支路径深入到不能再深入为止。

二叉树的深度优先遍历主要有三种：前序遍历、中序遍历和后序遍历。

下面我们以一道leetcode题来看看二叉树的深度优先遍历是如何实现的。

递归

当遇到深度优先遍历时，首先想到的是递归，而此题采用递归算法来实现二叉树的中序遍历还是比较简单的，直接看代码：

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        inorder(root, res);
        return res;
    }

    public void inorder(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }
        inorder(root.left, res);
        res.add(root.val);
        inorder(root.right, res);
    }
}

上面的res.add(root.val);如果放在inorder(root.left, res);之前，就是前序遍历；如果放在inorder(root.right, res);之后，就是后序遍历。

tip：如果是二叉树，那中序遍历的结果将是一个升序数组。

迭代

还有一种方法是采用迭代，这就需要借助到另外一种数据结构-栈。

其实上面的递归算法中，递归方法本身也属于栈，因此，我们可以在迭代方法中采用栈来代替递归。

首先，我们要清楚，中序遍历是先访问左子树，再访问自身，最后访问右节点。

所以，我们可以从根节点循环将左子树压入栈中，直到左子树为空，然后将左子树弹出的同时，再依次将右子树压入栈中。

这样就可以通过迭代来实现中序遍历。

下面看看代码是如何实现的：

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new LinkedList<>();
        Deque<TreeNode> deque = new LinkedList<>();
        while (root != null || !deque.isEmpty()) {
            // 循环将左子树压入栈中
            while (root != null) {
                deque.push(root);
                root = root.left;
            }
            root = deque.pop();
            res.add(root.val);
            root = root.right;
        }
        return res;
    }
}

广度优先遍历

英文缩写为BFS即Breadth FirstSearch。其过程检验来说是对每一层节点依次访问，访问完一层进入下一层，直到最后一层。

下面还是以leetcode中的题为例：

当看到这一题的时候，首先想到的就是一层一层的遍历，然后每遍历完一层以后，将这一层组成链表放入结果集中。

在二叉树的广度优先遍历中，需要借助到另外一种数据结构-队列。

在遍历队列时，同时将当前节点的左右子树加入队列中，当遍历完一层以后，下一层也刚好全部加入到队列中，这样就实现了二叉树一层一层的遍历。

下面看看代码是如何实现的：

class Solution {
    public ListNode[] listOfDepth(TreeNode tree) {
        if (tree == null) {
            return null;
        }
        List<ListNode> ans = new ArrayList<>();
        Queue<TreeNode> queue = new ArrayDeque<>();
        // 首先将根节点加入队列中
        queue.add(tree);
        while (!queue.isEmpty()) {
            // 最后加入集合中的需要是链表的头节点
            ListNode head = null;
            ListNode tail = null;
            // 遍历size长度，保证只遍历这一层数据
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                // 依次取出节点
                TreeNode treeNode = queue.poll();
                // 组成链表
                if (head == null) {
                    head = new ListNode(treeNode.val);
                    tail = head;
                } else {
                    tail.next = new ListNode(treeNode.val);
                    tail = tail.next;
                }
                // 将左右子节点加入队列中
                if (treeNode.left != null) {
                    queue.offer(treeNode.left);
                }
                if (treeNode.right != null) {
                    queue.offer(treeNode.right);
                }
            }
            // 将链表加入结果集中
            ans.add(head);
        }
        ListNode[] res = new ListNode[ans.size()];
        return ans.toArray(res);
    }
}

总结

最后总结一下，二叉树的遍历分为深度优先遍历和广度优先遍历。

深度优先遍历又分为，前序遍历、中序遍历和后序遍历，实现方式可采用递归和迭代+栈。

广度优先遍历的实现方式可采用迭代+队列。