欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCode:102.Binary Tree Level Order Traversal

程序员文章站 2024-02-19 13:54:22
...

题目要求如下:

Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).

For example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its level order traversal as:
[
[3],
[9,20],
[15,7]
]

大体的意思就是给你一个二叉树,用层次遍历的形式返回此二叉树。

一.我的解法

因为是要用层级遍历的形式返回二叉树,所以自然而然地想到了层级遍历,要注意每次遍历完一层后,要更新下每层结点的数量。时间复杂度是O(n),同时空间复杂度也是O(n)。

class Solution {
        public List<List<Integer>> levelOrder(TreeNode root) {
            List<List<Integer>> res=new ArrayList<>();
            Queue<TreeNode> queue=new LinkedList<>();
            int len=0;
            queue.offer(root);
            while(!queue.isEmpty()){
                List<Integer> ls=new ArrayList<>();
                len=queue.size();
                for(int i=0;i<len;i++){
                    TreeNode node=queue.poll();
                    if(node.left!=null)
                        queue.offer(node.left);
                    if(node.right!=null)
                        queue.offer(node.right);
                    ls.add(node.val);
                }
                res.add(new ArrayList<Integer>(ls));
            }
            return res;
        }
    }

二 .扩展

参考了一下LeetCode的讨论区的其他解法,发现除了利用BFS还可以用DFS去解决这个问题。好处是在空间减少了需要维护的队列,虽然时间复杂度上跟用BFS差不多。原理上就是先序遍历检查是否有下一层(即当前的结点子树不为空且当前的列表的子列表数目(代表目前已遍历过的层级)也小于height),有就继续进行下一层的先序遍历,没有则在同层级进行遍历。
这是原地址:https://discuss.leetcode.com/topic/4894/one-of-c-solutions-preorder

class Solution{
    List<List<Integer>> res=new ArrayList<>();
    public List<List<Integer>> levelOrder(TreeNode root){
        preorder(root,0);
        return res;
    }
    public void preorder(TreeNode root,int height){
        if(root==null) return;
        if(height>=res.size()){
            res.add(new ArrayList<Integer>());
        }
        res.get(height).add(root.val);
        preorder(root.left,height+1);
        preorder(root.right,height+1);
    }
}

我还是个菜鸟,如果有什么错误的地方或者想提的意见都可以评论,我会积极改进和吸收。

相关标签: OJ LeetCode 102