leetcode算法题解(Java版)-1-二叉树遍历

  1. 云栖社区>
  2. 博客列表>
  3. 正文

leetcode算法题解(Java版)-1-二叉树遍历

kissjz 2018-04-27 00:44:32 浏览7180 评论0

摘要: 又开始刷算法题了,正好在学Java,顺便也练练Java。

又开始刷算法题了,正好在学Java,顺便也练练Java。

题目描述

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,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:
[
[3],
[20,9],
[15,7]
]

confused what"{1,#,2,3}"means? > read more on how binary tree is serialized on OJ.

OJ's Binary Tree Serialization:
The serialization of a binary tree follows a level order traversal, where '#' signifies a path terminator where no node exists below.
Here's an example:

   1
  / \
 2   3
    /
   4
    \
     5

The above binary tree is serialized as"{1,2,3,#,#,4,#,#,5}".

我的解答

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Collections;
import java.util.Queue;

public class Solution {
    public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) {
        ArrayList<ArrayList<Integer>> ans=new ArrayList<>();
        if(root==null){
            return ans;
        }
        ArrayList<Integer> tem=new ArrayList<>();
        TreeNode lastNode=root;
        TreeNode levelNode=root;
        Queue<TreeNode> q=new LinkedList<>();
        q.add(root);
        int cnt=0;
        while(q.size()!=0){
            TreeNode poll=q.poll();
            tem.add((Integer)poll.val);
            if(poll.left!=null){
                q.offer(poll.left);
                lastNode=poll.left;
            }
            if(poll.right!=null){
                q.offer(poll.right);
                lastNode=poll.right;
            }
            if(levelNode==poll){
                if(cnt%2!=0){
                    Collections.reverse(tem);
                }
                levelNode=lastNode;
                ans.add(new ArrayList<>(tem));
                tem.clear();
                cnt++;
            }
        }
        return ans;
    }
}

遇到的坑&&小结:

  • 把Collections当成了Collection。实际上,Collections是一个包装类,可以当成专门为Collection中的类服务的工具类,不能被实例化;而Collection是根接口
  • Java引用变量有两个类型:一个是编译时的类型,一个是运行时的类型。编译时由声明该变量时使用的类型决定,运行时由实际赋值给它的对象的类型决定,当编译时的类型和运行时的类型不一样时,就产生了所谓的多态
  • 在多态中,引用类型时接口或父类,而正真的实现类型是实现接口的类的对象或继承父类的子类对象。比如:Queue<TreeNode> q=new LinkedList<>();其中,引用类型是Queue这个接口,实现类型(也就是运行时的类型)是LinkedList这个实现了Queue接口的类
  • 多态性是对象多种表现形式的体现
  • `ArrayList> res = new ArrayList>();
    一般都不这么写(我一开始不造),一般都写成ArrayList> res = new ArrayList<>();`因为不写默认跟前面的走,这是泛型规定的
【云栖快讯】你想见的Java技术专家都在这了,向大佬提问,有问题必答  详情请点击

网友评论

kissjz
文章250篇 | 关注114
关注
用于实时预测用户对物品偏好,支持企业定制推荐算法,支持A/B Test效果对比 查看详情
基于全网公开发布数据、传播路径和受众群体画像,利用语义分析、情感算法和机器学习,分析公众对品... 查看详情
大数据开发套件(Data IDE),提供可视化开发界面、离线任务调度运维、快速数据集成、多人... 查看详情
为您提供简单高效、处理能力可弹性伸缩的计算服务,帮助您快速构建更稳定、安全的应用,提升运维效... 查看详情
阿里云总监课正式启航

阿里云总监课正式启航