剑指offer刷题总结——树篇(三)

淡淡的烟草味﹌ 2021-09-21 03:34 313阅读 0赞

星级:1

1.按之字形顺序打印二叉树

【题目】

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

【代码】

  1. package swear2offer.tree;
  2. import java.util.ArrayList;
  3. import java.util.LinkedList;
  4. import java.util.Queue;
  5. public class T {
  6. /** * 请实现一个函数按照之字形打印二叉树,即 * 第一行按照从左到右的顺序打印, * 第二层按照从右至左的顺序打印, * 第三行按照从左到右的顺序打印,其他行以此类推。 * */
  7. public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
  8. if (pRoot == null) return new ArrayList<>();
  9. int i,index,size;
  10. TreeNode temp;
  11. Queue<TreeNode> q = new LinkedList<>();
  12. ArrayList<Integer> path = new ArrayList<>();
  13. ArrayList<ArrayList<Integer>> paths = new ArrayList<>();
  14. q.add(pRoot);
  15. path.add(pRoot.val);
  16. paths.add(path);
  17. index = 2;
  18. size = 0;
  19. while (!q.isEmpty()) {
  20. size = q.size();
  21. path = new ArrayList<>();
  22. // 通过size+循环的方式,省去复杂的判断
  23. for (i=0; i<size; i++) {
  24. temp = q.remove();
  25. if (temp.left != null) {
  26. if (index % 2 == 0) {
  27. path.add(0,temp.left.val);
  28. } else {
  29. path.add(temp.left.val);
  30. }
  31. q.add(temp.left);
  32. }
  33. if (temp.right != null) {
  34. if (index % 2 == 0) {
  35. path.add(0,temp.right.val);
  36. } else {
  37. path.add(temp.right.val);
  38. }
  39. q.add(temp.right);
  40. }
  41. }
  42. paths.add(path);
  43. index++;
  44. }
  45. paths.remove(paths.size()-1);
  46. return paths;
  47. }
  48. }

【思考】

通过判断每一行多少个节点来遍历每一行


2.二叉搜索树的第 k 个结点

【题目】

给定一棵二叉搜索树,请找出其中的第 k 小的结点。例如, (5,3,7,2,4,6,8) 中,按结点数值大小顺序第三小结点的值为 4。

【代码】

  1. package swear2offer.tree;
  2. import java.util.ArrayList;
  3. public class Kth {
  4. /** * 给定一棵二叉搜索树,请找出其中的第 k 小的结点。 * 例如,(5,3,7,2,4,6,8)中,按结点数值大小顺序第三小结点的值为 4。 * * 思路: * 先利用:左根右的中序遍历方式,获得排序数组,在输出第k位 * 优化:每次获得节点都计数,当存入第k个节点的时候,输出即可 * * 边界:k<1或者k大于树节点树 * */
  5. ArrayList<TreeNode> res;
  6. TreeNode KthNode (TreeNode pRoot, int k) {
  7. if (pRoot == null || k < 1) return null;
  8. res = new ArrayList<>();
  9. find(pRoot,k);
  10. if (res.size() < k) return null;
  11. return res.get(k-1);
  12. }
  13. public void find (TreeNode pRoot, int k) {
  14. if (pRoot!=null) {
  15. find(pRoot.left,k);
  16. res.add(pRoot);
  17. if (res.size() >= k) return;
  18. find(pRoot.right,k);
  19. }
  20. }
  21. }

【思考】

  • 思路: 先利用:左根右的中序遍历方式,获得排序数组,在输出第k位
  • 优化:每次获得节点都计数,当存入第k个节点的时候,输出即可
  • 边界:k<1或者k大于树节点树
  • 注意,无论任何排序,先中后序,操作都是对根节点,左右子树只是递归

发表评论

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

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

相关阅读