JZ60:把二叉树打印成多行

把二叉树打印成多行

http://www.nowcoder.com/practice/445c44d982d04483b04a54f298796288

解法1:增加两个TreeNode:last和nlast

  • last:表示当前遍历层最右结点
  • nlast:表示下一层最右结点

遍历时,每次将nlast指向插入队列元素,最后一个插入结点时即最右结点。插入左右孩子之后,检测last是否为当前输出结点,若是,则表示需要进行换行,并将last指向下一层的nlast。

public class Solution {
    ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> list=new ArrayList<ArrayList<Integer>>();
        if(pRoot==null){
            return list;
        }
        Queue<TreeNode> queue=new LinkedList<TreeNode>();
        queue.add(pRoot);
        TreeNode last=pRoot;
        TreeNode nlast=pRoot;
        ArrayList<Integer> res=new ArrayList<Integer>();
        while(!queue.isEmpty()){
            TreeNode tmp=queue.poll();
            res.add(tmp.val);

            if(tmp.left!=null){
                queue.add(tmp.left);
                nlast=tmp.left;
            }
            if(tmp.right!=null){
                queue.add(tmp.right);
                nlast=tmp.right;
            }
            if(tmp==last){
                list.add(res);
                last=nlast;
                res=new ArrayList<Integer>();
            }
        }
        return list;
    }

}

解法2:根据层次遍历的顺序,每一层都是从左到右的遍历输出,借助于一个队列。

先将根节点入队,当前节点是队头节点,将其出队并访问,如果当前节点的左节点不为空将左节点入队,如果当前节点的右节点不为空将其入队。所以出队顺序也是从左到右依次出队。

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
public class Solution {
    public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
         ArrayList<ArrayList<Integer>> result = new ArrayList<>();
         if (root == null) {
            return result;
        }
         Queue<TreeNode> queue = new LinkedList<>();
         queue.add(root);
         while(!queue.isEmpty()) {
             ArrayList<Integer> list = new ArrayList<>();
             int size = queue.size();
             for (int i = 0; i < size; i++) {
                TreeNode temp = queue.poll();
                list.add(temp.val);
                if (temp.left != null) {
                    queue.add(temp.left);
                }
                if (temp.right != null) {
                    queue.add(temp.right);
                }
            }
             //result.add(0,list);
             result.add(list);
         }
         return result;
    }
}
剑指Offer题解 文章被收录于专栏

剑指Offer-Java版本题解

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
2022-12-29 23:08
浙江大学_2021
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-23 19:49
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-20 17:21
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议