【剑指offer】面试题32:从上到下打印二叉树

旧城等待, 2022-03-29 09:17 280阅读 0赞

题目1:不分行从上到下打印二叉树。从上往下打印出二叉树的每个节点,同一层的节点从左到右的顺序打印。

牛客网链接:https://www.nowcoder.com/questionTerminal/7fe2212963db4790b57431d9ed259701

例如输入下图的二叉树,则依次打印出:8,6,10,5,7,9,11。

20190108093729727.png

这道题实质上考察的就是树的遍历算法,只是这种遍历不是我们熟悉的前序、中序或者后序遍历。由于我们不太熟悉这种按层遍历的方法,可能一下子也想不清楚遍历的过程。

因为按层打印的顺序决定应该先打印的根节点,所以我们从树的根节点开始分析。为了接下来能够打印8的结点的两个子节点,我们应该在遍历到该结点时把值为6和10的两个结点保存到一个容器中,现在容器内就有两个结点了。按照从左到右打印的要求,我们先取出值为6的结点。打印出6后把它的值分别为5和7的两个结点放入数据容器。此时数据容器中有3个结点,值分别为10,5,7。接下来我们从数据容器中取出值为10的结点。注意到值为10的结点比值为5、7的结点先放入容器,此时又比这两个结点先取出,这就是我们通常说的**先入先出**,因此不难看出这个容器应该是一个**队列**。由于值为5,7,9,11的结点都没有子节点,因此只要依次打印即可。

通过分析具体例子,我们可以找到从上到下打印二叉树的规律:每次打印一个结点的时候,如果该节点有子节点,把该节点的子节点放到一个队列的末尾。接下来到队列的头部取出最早进入队列的节点,重复前面打印操作,直到队列中所有的节点都被打印出来。

代码实现:

  1. package com.zju.offer.tree;
  2. import java.util.ArrayList;
  3. /**
  4. * 不分行从上到下打印二叉树
  5. * 从上往下打印出二叉树的每个节点,同一层的节点从左到右的顺序打印
  6. */
  7. public class PrintFromTopToBottom {
  8. public class TreeNode {
  9. int val = 0;
  10. TreeNode left = null;
  11. TreeNode right = null;
  12. public TreeNode(int val) {
  13. this.val = val;
  14. }
  15. }
  16. public ArrayList<Integer> printFromTopToBottom(TreeNode root){
  17. ArrayList<Integer> list = new ArrayList<>();
  18. // 模拟一个队列,也可以用LinkedList
  19. ArrayList<TreeNode> queue = new ArrayList<>();
  20. if(root == null){
  21. return list;
  22. }
  23. queue.add(root);
  24. while(queue.size() != 0){
  25. // 将queue中第一个元素移除
  26. TreeNode temp = queue.remove(0);
  27. // 如果将要移除的节点有左子节点,则加入queue
  28. if(temp.left != null){
  29. queue.add(temp.left);
  30. }
  31. // 如果将要移除的节点有右子节点,则加入queue
  32. if(temp.right != null){
  33. queue.add(temp.right);
  34. }
  35. // 将temp的值加入list中
  36. list.add(temp.val);
  37. }
  38. return list;
  39. }
  40. }

本题实现代码中用的是一个ArrayList集合去模拟的队列,每次移除下标为0的元素即为队列的头元素,也符合队列“先进先出的特点”。

20190108105202217.png

本题扩展:如何广度优先遍历一幅有向图?同样也可以基于队列实现。树是图的一种特殊退化形式,从上到下按层遍历二叉树,从本质上来说就是广度优先遍历二叉树。

举一反三:不管是广度优先遍历一幅有向图还是一棵树,都要用到队列。首先把起始节点(对树而言是根节点)放入队列。接下来每次从队列的头部取出一个节点,遍历这个节点之后把它能到达的节点(对树而言是子节点)都依次放入到队列。重复这个遍历过程,直到队列中的节点全部被遍历为止。

题目2:分行从上到下打印二叉树。从上到下按层打印二叉树,同一层的节点按从左到右的顺序打印,每一层打印到一行。

如下案例所示:

20190108093729727.png

打印结果为:

8

6 10

5 7 9 11

这道题和前面的题类似,也可以用一个队列来保存将要打印的节点。为了把二叉树的每一行单独打印到一行里,我们需要两个变量:一个变量表示在当前层中还没有打印的节点数;另外一个变量表示下一层节点的数目。

  1. public class PrintFromTopToBottom {
  2. public class TreeNode {
  3. int val = 0;
  4. TreeNode left = null;
  5. TreeNode right = null;
  6. public TreeNode(int val) {
  7. this.val = val;
  8. }
  9. }
  10. public ArrayList<Integer> printFromTopToBottom_Method1(TreeNode root){
  11. ArrayList<Integer> list = new ArrayList<>();
  12. // 模拟一个队列,也可以用LinkedList
  13. ArrayList<TreeNode> queue = new ArrayList<>();
  14. if(root == null){
  15. return list;
  16. }
  17. queue.add(root);
  18. int nextLevel = 0;
  19. int toBePrinted = 1;
  20. while(queue.size() != 0){
  21. // 将queue中第一个元素移除
  22. TreeNode temp = queue.remove(0);
  23. // 如果将要移除的节点有左子节点,则加入queue
  24. if(temp.left != null){
  25. queue.add(temp.left);
  26. nextLevel++;
  27. }
  28. // 如果将要移除的节点有右子节点,则加入queue
  29. if(temp.right != null){
  30. queue.add(temp.right);
  31. nextLevel++;
  32. }
  33. // 将temp的值加入list中
  34. list.add(temp.val);
  35. System.out.print(temp.val + " ");
  36. --toBePrinted;
  37. if(toBePrinted == 0){
  38. System.out.println();
  39. toBePrinted = nextLevel;
  40. nextLevel = 0;
  41. }
  42. }
  43. return list;
  44. }
  45. // 测试
  46. public static void main(String[] args) {
  47. PrintFromTopToBottom p = new PrintFromTopToBottom();
  48. TreeNode root = p.new TreeNode(8);
  49. TreeNode node1 = p.new TreeNode(6);
  50. TreeNode node2 = p.new TreeNode(10);
  51. TreeNode node3 = p.new TreeNode(5);
  52. TreeNode node4 = p.new TreeNode(7);
  53. TreeNode node5 = p.new TreeNode(9);
  54. TreeNode node6 = p.new TreeNode(11);
  55. root.left = node1;
  56. root.right = node2;
  57. node1.left = node3;
  58. node1.right = node4;
  59. node2.left = node5;
  60. node2.right = node6;
  61. p.printFromTopToBottom_Method1(root);
  62. }
  63. }

变量 toBePrinted 表示在当前层中还没有打印的节点数,而变量 nextLevel 表示下一层的节点数。如果一个节点有子节点,则每把一个子节点加入队列,同时把变量 nextLevel 加1。每打印一个节点,toBePrinted 减 1。当 toBePrinted 变成 0 时,表示当前层的所有节点已经打印完毕,可以继续打印下一层。

题目3:之字形打印二叉树。

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

按之字形顺序打印二叉树需要两个栈。我们在打印某一层的节点时,把下一层的子节点保存到相应的栈里。如果当前打印的是奇数层(第一层、第三层等),则先保存左子节点再保存右子节点到第一个栈里(因为栈的后进先出特点);如果当前打印的是偶数层(第二层、第四层等),则先保存右子节点再保存左子节点到第二个栈里。接下来逐个把位于栈顶的节点弹出栈并打印即可。

使用嵌套集合类型来保存 stack1 和 stack2 中弹出的数据,每一个内层小集合中保存一层的数据。

  1. package com.zju.offer.tree;
  2. import java.util.ArrayList;
  3. import java.util.Stack;
  4. public class PrintFromTopToBottom {
  5. public class TreeNode {
  6. int val = 0;
  7. TreeNode left = null;
  8. TreeNode right = null;
  9. public TreeNode(int val) {
  10. this.val = val;
  11. }
  12. }
  13. /**
  14. * 之字形打印:奇数从左往右打印、偶数从右往左打印
  15. */
  16. public ArrayList<ArrayList<Integer>> Print(TreeNode root){
  17. // 层数索引
  18. int layer = 1;
  19. // stack1 保存奇数层节点
  20. Stack<TreeNode> stack1 = new Stack<TreeNode>();
  21. stack1.push(root); // 因为根节点是奇数层,所以将根节点先保存到stack1中
  22. // stack2 保存偶数层节点
  23. Stack<TreeNode> stack2 = new Stack<TreeNode>();
  24. // 采用双层集合,每一个内层集合存储一层数据
  25. ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
  26. while(!stack1.empty() || !stack2.empty()){
  27. if(layer % 2 != 0){
  28. // 打印奇数层
  29. ArrayList<Integer> temp = new ArrayList<Integer>();
  30. while(!stack1.empty()){
  31. TreeNode node = stack1.pop();
  32. if(node != null){
  33. temp.add(node.val);
  34. System.out.print(node.val + " ");
  35. // 由于当前层是奇数层,所以它的下一层是要从右往左打印
  36. // 因此按照栈的"后进先出"的特性,先保存左子节点,再保存右子节点
  37. stack2.push(node.left);
  38. stack2.push(node.right);
  39. }
  40. }
  41. if(!temp.isEmpty()){
  42. list.add(temp);
  43. layer++;
  44. System.out.println();
  45. }
  46. }else{
  47. // 打印偶数层
  48. ArrayList<Integer> temp = new ArrayList<Integer>();
  49. while(!stack2.isEmpty()){
  50. TreeNode node = stack2.pop();
  51. if(node != null){
  52. temp.add(node.val);
  53. System.out.print(node.val + " ");
  54. // 由于当前层是偶数层,所以它的下一层是要从左往右打印
  55. // 因此按照栈的"后进先出"的特性,先保存右子节点,再保存左子节点
  56. stack1.push(node.right);
  57. stack1.push(node.left);
  58. }
  59. }
  60. if(!temp.isEmpty()){
  61. list.add(temp);
  62. layer++;
  63. System.out.println();
  64. }
  65. }
  66. }
  67. return list;
  68. }
  69. // 测试
  70. public static void main(String[] args) {
  71. PrintFromTopToBottom p = new PrintFromTopToBottom();
  72. TreeNode root = p.new TreeNode(8);
  73. TreeNode node1 = p.new TreeNode(6);
  74. TreeNode node2 = p.new TreeNode(10);
  75. TreeNode node3 = p.new TreeNode(5);
  76. TreeNode node4 = p.new TreeNode(7);
  77. TreeNode node5 = p.new TreeNode(9);
  78. TreeNode node6 = p.new TreeNode(11);
  79. root.left = node1;
  80. root.right = node2;
  81. node1.left = node3;
  82. node1.right = node4;
  83. node2.left = node5;
  84. node2.right = node6;
  85. p.Print(root);
  86. }
  87. }

发表评论

表情:
评论列表 (有 0 条评论,280人围观)

还没有评论,来说两句吧...

相关阅读