题目描述

给定一个二叉树,返回其按层次遍历的节点值。 (即逐层地,从左到右访问所有节点)。

例如:
给定二叉树: [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

返回其层次遍历结果:

[
  [3],
  [9,20],
  [15,7]
]

https://leetcode-cn.com/problems/binary-tree-level-order-traversal/

解法1 – BFS

解法1不用多说,在课本中,考研题中经常出现。我们使用队列,将跟节点加入队列,然后出队并访问,再将出队节点的左右子树再一次加入队列……直到队列为空。这种解法很自然,也很容易想到。

时间复杂度O(n),空间复杂度O(n)。全部代码如下:

import java.util.*;

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();

        if (root == null)
            return ans;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            List<Integer> list = new ArrayList<>();
            int size = queue.size();
       
            while (size-- > 0) {
                TreeNode node = queue.poll();

                list.add(node.val);
                if (node.left != null)
                    queue.offer(node.left);
                if (node.right != null)
                    queue.offer(node.right);
            }
            ans.add(list);
        }

        return ans;
    }
}

解法2 – DFS

这道题也可以采用DFS解法,层次其实就是深度,我们记录遍历到每一层级到深度,为每一层级创建List,根据当前深度找到对应的List,然后追加进去。在实现的时候,我们采用先序遍历的,如果采用中序/后序遍历,下面的代码需要略微调整,将if改为while。因为先序遍历能够保证为深度比当前节点浅的所有节点都创建相应的List。而中序/后序遍历会先走到最深的左/右子树,我们必须使用循环为所有层级比当前浅的节点创建对应的List。

DFS理论上会比BFS慢一些,因为存在函数调用与调用栈创建等开销。此外,如果树的层级过高,会有“爆栈”的风险。时间复杂度O(n),空间复杂度O(n)。全部代码如下:

import java.util.*;

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();

        levelOrderHelper(root, 0, ans);

        return ans;
    }

    private void levelOrderHelper(TreeNode root, int depth, List<List<Integer>> ans) {
        if (root == null)
            return;
        // 如果采用中/后序遍历,需要将if改成while
        if (depth >= ans.size())
            ans.add(new ArrayList<>());

        ans.get(depth).add(root.val);

        levelOrderHelper(root.left, depth + 1, ans);
        levelOrderHelper(root.right, depth + 1, ans);
    }
}
pwrliang Algorithms, BFS, DFS, Tree ,

Leave a Reply

Your email address will not be published. Required fields are marked *