LeetCode 102 & 103 &107 & 637. Binary Tree Level Order Traversal

背景知识:

层序遍历二叉树

最为经典的解法就是借助队列,方法如下:

 public void levelOrderTraversal(TreeNode root){
        if (root == null ) return;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()){
            TreeNode node = queue.remove();
            System.out.println(node.val);
            if (node.left !=null) queue.add(node.left);
            if (node.right !=null) queue.add(node.right);
        }
    }

102. Binary Tree Level Order Traversal

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]
]

题目大意:层序遍历一个二叉树

解法一:

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

解法二:

   public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        HashMap<Integer,ArrayList<Integer>> map = new HashMap<>();
        levelOrderBottomHelper(root,map,1);
        for (int i = 1 ;i <=map.size() ;i++){
           res.add(map.get(i));
        }
        return res;
    }

    public void levelOrderBottomHelper(TreeNode root,HashMap<Integer,ArrayList<Integer>> map,int level){
        if (root == null ) return;
        if (map.containsKey(level)){
            map.get(level).add(root.val);
        }else {
            ArrayList<Integer> list = new ArrayList<>();
            list.add(root.val);
            map.put(level,list);
        }
        levelOrderBottomHelper(root.left,map,level+1);
        levelOrderBottomHelper(root.right,map,level+1);
    }

107.Binary Tree Level Order Traversal II

Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).

For example: Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its bottom-up level order traversal as:

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

解法一:

public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null ) return res;
        Stack<List<Integer>> stack = new Stack<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()){
            List<Integer> resTemp = new ArrayList<>();
            int size = queue.size();
            for (int i = 0;i<size;i++){
                TreeNode node = queue.remove();
                resTemp.add(node.val);
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            stack.push(resTemp);
        }
        while (!stack.isEmpty()){
            res.add(stack.pop());
        }
        System.out.println(res);
        return res;
    }

解法二:

    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        HashMap<Integer,ArrayList<Integer>> map = new HashMap<>();
        levelOrderBottomHelper(root,map,1);
        for (int i = map.size() ;i > 0 ;i--){
           res.add(map.get(i));
        }
        return res;
    }

    public void levelOrderBottomHelper(TreeNode root,HashMap<Integer,ArrayList<Integer>> map,int level){
        if (root == null ) return;
        if (map.containsKey(level)){
            map.get(level).add(root.val);
        }else {
            ArrayList<Integer> list = new ArrayList<>();
            list.add(root.val);
            map.put(level,list);
        }
        levelOrderBottomHelper(root.left,map,level+1);
        levelOrderBottomHelper(root.right,map,level+1);
    }

637. Average of Levels in Binary Tree

Given a non-empty binary tree, return the average value of the nodes on each level in the form of an array.

Example 1:

Input:
    3
   / \
  9  20
    /  \
   15   7
Output: [3, 14.5, 11]
Explanation:
The average value of nodes on level 0 is 3,  on level 1 is 14.5, and on level 2 is 11. 
Hence return [3, 14.5, 11].

题目大意:对二叉树的每一层的节点取平均值。

解法:

  public List<Double> averageOfLevels(TreeNode root) {
        List<Double> res = new ArrayList<>();
        Queue<TreeNode> queue= new LinkedList<>();
        if (root == null) return null;
        queue.add(root);
        while (!queue.isEmpty()){
            int n = queue.size();
            double sum = 0.0;
            for (int i = 0 ; i < n;i++){
               TreeNode temp = queue.remove();
               sum += temp.val;
               if (temp.left != null) queue.add(temp.left) ;
               if (temp.right != null) queue.add(temp.right);
            }
            res.add(sum/n);
        }
        return res;
    }

103. Binary Tree Zigzag Level Order Traversal

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

For example: Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:

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

题目大意:之字形的遍历一个二叉树。

解法一:

在102题的基础上,写一个LinkedList的reverse函数将奇数的结果翻转一下就可以了

总结:

这几个题目的思路有相同之处,如果涉及到对于二叉树的每一层的数据进行处理,上述解法是一个非常典型的解决方式,即在while里面加上一个for循环,每次for循环结束都是将某一行的数据处理完。还有一种方法是采用HashMap,让level作为key值,这样每一个节点都会记录他所在的层数。

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏编程理解

数据结构(三):二叉树遍历

前序遍历的方式,也就是对每一棵子树,按照根节点、左子树、右子树的顺序进行访问,也就是根-左-右的访问顺序。因为每一棵非空子树,又可拆分为根节点、左子树和右子树,...

1912
来自专栏我是东东强

常见算法之二叉树遍历

所谓遍历二叉树,就是遵从某种次序,顺着某一条搜索路径访问二叉树中的各个结点,使得每个结点均被访问一次,而且仅被访问一次。本文详细介绍了二叉树的前序(又称先序)、...

1462
来自专栏Java呓语

迭代器模式(控制访问集合中的元素)

现在我们需要思索,JDK是怎么做到这一切的?现在让我们先利用迭代器实现一个数组类型Array,这个类型需要支持添加、移除、遍历操作。

1052
来自专栏xingoo, 一个梦想做发明家的程序员

B树 B-树 B+树 B*树

B树 即二叉搜索树:        1.所有非叶子结点至多拥有两个儿子(Left和Right);        2.所有结点存储一个关键字;        3...

2057
来自专栏用户画像

4.5.1 二叉排序树

二叉排序树的查找时从根结点开始,沿着某一分支逐层向下进行比较比较的过程。若二叉排序树非空,将给定值与根结点的关键字比较,若相等,则查找成功;若不等,则当根结点的...

1113
来自专栏Android机动车

数据结构——遍历二叉树

二叉树的遍历:是指从根结点出发,按照某种次序依次访问二叉树中的所有结点,使得每个结点被访问一次且仅被访问一次。

961
来自专栏从流域到海域

二叉树的性质和常用操作代码集合

二叉树的性质和常用操作代码集合 性质: 二叉树的性质和常用代码操作集合 性质1:在二叉树的第i层上至多有2^i-1个结点 性质2:...

2339
来自专栏博岩Java大讲堂

Java集合--List源码

2554
来自专栏mukekeheart的iOS之旅

二叉树的基本概念和遍历

一、二叉树的基本概念 平衡二叉树:如果一棵树不为空,并且其中所有的子树都满足各自的左子树与右子树的高度差都不超过1。(空树是平衡二叉树)  1 //判断二叉树...

25610
来自专栏Android机器圈

数据结构与算法 -- 二叉树链式详解((非)/递归遍历,叶子个数,深度计算)

PS:树型结构是一种重要的非线性数据结构,教科书上一般都是树与二叉树,由此可见,树和二叉树是有区别和联系的,网上有人说二叉树是树的一种特殊形式,但经过查资料,树...

1035

扫码关注云+社区

领取腾讯云代金券