剑指offer—二叉树多行打印和之字形打印 解答

剑指offer—二叉树多行打印和之字形打印

首先看到二叉树遍历我们可以优先想到深搜和广搜,但是一看是按层次遍历,我们就可以选择广搜

二叉树单行打印

也就是按照层次从左到右依次打印二叉树,全部存储在一个列表或者数组中

思路

选择使用广搜的话,我们只需要使用一个队列来实现,首先对根节点进行入队,出队的时候把它的左孩子节点和右孩子节点依次入队,直到队列为空就返回该列表就是最终的遍历结果

代码

public class Solution {
    ArrayList<ArrayList<Integer> > Print(TreeNode head) {
        LinkedList<TreeNode> q = new LinkedList<>();
        ArrayList<Integer> re = new ArrayList<>();
        q.add(head);
        while(!q.isEmpty()){
            TreeNode node = q.pop();
            level.add(node.val);
            if(node.left!=null) q.add(node.left);
            if(node.right!=null) q.add(node.right);
        }
        return re;
    }
}

二叉树多行打印

从上到下按层打印二叉树,同一层结点从左至右输出。每一层输出一行。

思路

按照上一题的思路,我们使用广搜可以完成单行打印,但是我们需要的是多行打印的话就比较困难了,因为我们都知道二叉树广搜是无法获取到每个层次的最后一个节点的,我们需要知道每一层次的最后一个节点才能去把每一行的数据加入到单独的列表中

  • 如何获取每一行的最后一个节点

首先我们知道二叉树的每一层最后一个节点的右孩子不为空的话就一定是下一层的最后一个节点,我们利用这个特性可以从根节点开始,根节点的右孩子节点不为空的话就是下一层的最后一个节点。

按照这样的思路我们需要维护一个节点tail保存每一行的最后一个节点,起始为根节点,如果出队时碰到该根节点,就创建一个新的list开始下一层的遍历;这么一看可以用,但是者有很大一个问题就是,这种做法只是针对完全二叉树时使用,如果不是完全二叉树,如下面这样一颗二叉树,那么它判断到tail节点为null时就判断它为最后一层了,但是其实这不是最后一层

这个时候我们按照这种方法扩展一下思路,能不能利用队列特性在每一层结束时放入一个标志,如果遇到这个标志时我们就从新开始一行遍历

我们一想就想到了在我们每一层最后一个节点出队时再入队一个标志位可不可以,这时它的左右节点在这个标志位入队前入队,想一想,我们下一次出队这个标志位是什么时候?

那根据队列性质,下一次出队该标志位一定就是下一层全部遍历完成的时候,叮叮叮———

在根节点入队后,因为他是第一层最后一个节点,所以我们在它后面在入队一个标志位用null来统一该标志位,当下一次出队时节点为null时,说明来到了我们的标志位,那么说明该层遍历结束了,我们需要开始一次新的层次遍历,所以我们需要再在其后面插入一个null标志位;利用这个标志位我们就可以很好的判断是否为该层的最后一个节点;相比上一种方法,这种方法结合了队列的特性,即使不是完全二叉树也可以根据队列出队结果判断方是否为该层最后一个节点

代码

public class Solution {
    ArrayList<ArrayList<Integer> > Print(TreeNode head) {
        LinkedList<TreeNode> q = new LinkedList<>();
        ArrayList<ArrayList<Integer>> re = new ArrayList<>();
        q.add(head);
        q.add(null);
        ArrayList<Integer> level = new ArrayList<>();
        while(!q.isEmpty()){
            if(q.peek()==null){
                q.add(null);
                if(level.isEmpty()) break;
                re.add(level);
                level = new ArrayList<>();
                q.pop();
                continue;
            }
            TreeNode node = q.pop();
            level.add(node.val);
            if(node.left!=null) q.add(node.left);
            if(node.right!=null) q.add(node.right);
        }
        return re;
    }
}

二叉树之字形打印

请实现一个函数按照之字形打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右至左的顺序打印,第三行按照从左到右的顺序打印,其他行以此类推。

思路

这题思路和上一题类似,只不过我们注意到不同的地方就是之字形要求的是奇数行从左到右打印,偶数行从右到左打印,我们可以定义一个boolean变量,在每行结束后把该boolean标志取反,每次添加list到最终集合中时,判断如果boolean标志位为true就需要对list进行reverse操作,如果为false就不需要操作,这样就可以保证每一次添加list到最终集合中时,都和上一次插入的list顺序相反,就保证了奇数行插入的是从右到左,偶数行插入的是从左到右

  • reverse操作:Collections.reverse(list);

代码

public class Solution {
    public ArrayList<ArrayList<Integer> > Print(TreeNode head) {
        LinkedList<TreeNode> q = new LinkedList<>();
        ArrayList<ArrayList<Integer>> re = new ArrayList<>();
        q.add(head);
        q.add(null);//标志
        ArrayList<Integer> level = new ArrayList<>();
        boolean flag = false;
        while(!q.isEmpty()){
            if(q.peek()==null){
                q.add(null);
                if(level.isEmpty()) break;
                if(flag) Collections.reverse(level);
                re.add(level);
                level = new ArrayList<>();
                q.pop();
                flag = !flag;
                continue;
            }
            TreeNode node = q.pop();
            level.add(node.val);
            if(node.left!=null) q.add(node.left);
            if(node.right!=null) q.add(node.right);
        }
        return re;
    }
}
  • 本文作者: dzou | 微信:17856530567
  • 本文链接: http://www.dzou.top/post/rows-btree.html
  • 版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处!
  • 并保留本声明和上方二维码。感谢您的阅读和支持!