递归方式需要理解递归序

先序遍历

任何子树的处理顺序都是，先头结点、再左子树、然后右子树

  1. public static void pre(Node head) {
  2.     if (head == null) {
  3.         return;
  4.     }
  5.     System.out.println(head.value);
  6.     pre(head.left);
  7.     pre(head.right);
  8. }
  1. public static void pre(Node head) {
  2.     System.out.print("pre-order: ");
  3.     if (head != null) {
  4.         Stack<Node> stack = new Stack<Node>();
  5.         stack.add(head);
  6.         while (!stack.isEmpty()) {
  7.             head = stack.pop();
  8.             System.out.print(head.value + " ");
  9.             if (head.right != null) {
  10.                 stack.push(head.right);
  11.             }
  12.             if (head.left != null) {
  13.                 stack.push(head.left);
  14.             }
  15.         }
  16.     }
  17.     System.out.println();
  18. }

中序遍历

任何子树的处理顺序都是，先左子树、再头结点、然后右子树

  1. public static void in(Node head) {
  2.     if (head == null) {
  3.         return;
  4.     }
  5.     in(head.left);
  6.     System.out.println(head.value);
  7.     in(head.right);
  8. }
  1. public static void in(Node cur) {
  2.     System.out.print("in-order: ");
  3.     if (cur != null) {
  4.         Stack<Node> stack = new Stack<Node>();
  5.         while (!stack.isEmpty() || cur != null) {
  6.             if (cur != null) {
  7.                 stack.push(cur);
  8.                 cur = cur.left;
  9.             } else {
  10.                 cur = stack.pop();
  11.                 System.out.print(cur.value + " ");
  12.                 cur = cur.right;
  13.             }
  14.         }
  15.     }
  16.     System.out.println();
  17. }

后续遍历

任何子树的处理顺序都是，先左子树、再右子树、然后头结点

  1. public static void pos(Node head) {
  2.     if (head == null) {
  3.         return;
  4.     }
  5.     pos(head.left);
  6.     pos(head.right);
  7.     System.out.println(head.value);
  8. }
  1. public static void pos1(Node head) {
  2.     System.out.print("pos-order: ");
  3.     if (head != null) {
  4.         //利用栈的来逆序  头右左 -> 左右头
  5.         Stack<Node> s1 = new Stack<Node>();
  6.         Stack<Node> s2 = new Stack<Node>();
  7.         s1.push(head);
  8.         while (!s1.isEmpty()) {
  9.             head = s1.pop(); // 头 右 左
  10.             s2.push(head);
  11.             if (head.left != null) {
  12.                 s1.push(head.left);
  13.             }
  14.             if (head.right != null) {
  15.                 s1.push(head.right);
  16.             }
  17.         }
  18.         // 左 右 头
  19.         while (!s2.isEmpty()) {
  20.             System.out.print(s2.pop().value + " ");
  21.         }
  22.     }
  23.     System.out.println();
  24. }
  1. public static void pos2(Node h) {
  2.     System.out.println("pos-order: ");
  3.     if (h != null) {
  4.         Stack<Node> stack = new Stack<>();
  5.         stack.push(h);
  6.         Node c = null;
  7.         while (!stack.isEmpty()) {
  8.             c = stack.peek();
  9.             if (c.left != null && h != c.left && h != c.right) {
  10.                 stack.push(c.left);
  11.             } else if (c.right != null && h != c.right) {
  12.                 stack.push(c.right);
  13.             }else {
  14.                 System.out.print(stack.pop().value + " ");
  15.                 h = c;
  16.             }
  17.         }
  18.     }
  19.     System.out.println();
  20. }

加深理解

（证明）在二叉树中给定一个节点X，先序遍历中X左边的节点集合与后续遍历中X右边节点集合的交集一定都是X节点的祖先节点

1、X的孩子节点不会出现在交集中 先序：头 X 左右 后续：左右 X 头 2、X作为左树姿态下右兄节点不会出现在先序遍历中X左侧节点集合 先序：头左右 X 3、X作为右树姿态下左兄节点不会出现在后序遍历中X右侧侧节点集合 后续：左右头 X

宽度优先遍历

  1. public static void level(Node head) {
  2.     if (head == null) {
  3.         return;
  4.     }
  5.     Queue<Node> queue = new LinkedList<>();
  6.     queue.add(head);
  7.     while (!queue.isEmpty()) {
  8.         Node curr = queue.poll();
  9.         System.out.println(curr.value);
  10.         if (curr.left != null) {
  11.             queue.add(curr.left);
  12.         }
  13.         if (curr.right != null) {
  14.             queue.add(curr.right);
  15.         }
  16.     }
  17. }

给定一颗二叉树，输出最宽层的宽度

  1. //思路，遍历过程中记录每个节点的层数是第几层
  2. public static int maxWidthUseMap(Node head) {
  3.     if (head == null) {
  4.         return 0;
  5.     }
  6.     Queue<Node> queue = new LinkedList<>();
  7.     queue.add(head);
  8.     // key 在 哪一层，value
  9.     HashMap<Node, Integer> levelMap = new HashMap<>();
  10.     levelMap.put(head, 1);
  11.     int curLevel = 1; // 当前你正在统计哪一层的宽度
  12.     int curLevelNodes = 0; // 当前层curLevel层，宽度目前是多少
  13.     int max = 0;
  14.     while (!queue.isEmpty()) {
  15.         Node cur = queue.poll();
  16.         int curNodeLevel = levelMap.get(cur);
  17.         if (cur.left != null) {
  18.             levelMap.put(cur.left, curNodeLevel + 1);
  19.             queue.add(cur.left);
  20.         }
  21.         if (cur.right != null) {
  22.             levelMap.put(cur.right, curNodeLevel + 1);
  23.             queue.add(cur.right);
  24.         }
  25.         if (curNodeLevel == curLevel) {
  26.             curLevelNodes++;
  27.         } else {
  28.             max = Math.max(max, curLevelNodes);
  29.             curLevel++;
  30.             curLevelNodes = 1;
  31.         }
  32.     }
  33.     max = Math.max(max, curLevelNodes);
  34.     return max;
  35. }
  1. public static int maxWidthNoMap(Node head) {
  2.     if (head == null) {
  3.         return 0;
  4.     }
  5.     Queue<Node> queue = new LinkedList<>();
  6.     queue.add(head);
  7.     Node curEnd = head; // 当前层，最右节点是谁
  8.     Node nextEnd = null; // 下一层，最右节点是谁
  9.     int max = 0;
  10.     int curLevelNodes = 0; // 当前层的节点数
  11.     while (!queue.isEmpty()) {
  12.         Node cur = queue.poll();
  13.         if (cur.left != null) {
  14.             queue.add(cur.left);
  15.             nextEnd = cur.left;
  16.         }
  17.         if (cur.right != null) {
  18.             queue.add(cur.right);
  19.             nextEnd = cur.right;
  20.         }
  21.         curLevelNodes++;
  22.         if (cur == curEnd) {
  23.             max = Math.max(max, curLevelNodes);
  24.             curLevelNodes = 0;
  25.             curEnd = nextEnd;
  26.         }
  27.     }
  28.     return max;
  29. }

二叉树的序列化与反序列化

二叉树可以通过先序、后序或者按层遍历的方式序列化和反序列化，
但是，二叉树无法通过中序遍历的方式实现序列化和反序列化
因为不同的两棵树，可能得到同样的中序序列，即便补了空位置也可能一样。
比如如下两棵树
2
/
1
和
1
\
2
补足空位置的中序遍历结果都是{ null, 1, null, 2, null}

  1. //序列化
  2. public static Queue<String> preSerial(Node head) {
  3.     Queue<String> ans = new LinkedList<>();
  4.     pres(head, ans);
  5.     return ans;
  6. }
  8. public static void pres(Node head, Queue<String> ans) {
  9.     if (head == null) {
  10.         ans.add(null);
  11.     } else {
  12.         ans.add(String.valueOf(head.value));
  13.         pres(head.left, ans);
  14.         pres(head.right, ans);
  15.     }
  16. }
  19. //反序列化
  20. public static Node buildByPreQueue(Queue<String> preList) {
  21.     if (preList == null || preList.isEmpty()) {
  22.         return null;
  23.     }
  24.     return preb(preList);
  25. }
  27. private static Node preb(Queue<String> preList) {
  28.     String val = preList.poll();
  29.     if (val == null) {
  30.         return null;
  31.     }
  32.     Node node = new Node(Integer.valueOf(val));
  33.     node.left = preb(preList);
  34.     node.right = preb(preList);
  35.     return node;
  36. }
  1. //序列化
  2. public static Queue<String> posSerial(Node head) {
  3.     Queue<String> ans = new LinkedList<>();
  4.     poss(head, ans);
  5.     return ans;
  6. }
  8. public static void poss(Node head, Queue<String> ans) {
  9.     if (head == null) {
  10.         ans.add(null);
  11.     } else {
  12.         poss(head.left, ans);
  13.         poss(head.right, ans);
  14.         ans.add(String.valueOf(head.value));
  15.     }
  16. }
  18. //反序列化
  19. public static Node buildByPosQueue(Queue<String> posList) {
  20.     if (posList == null || posList.isEmpty()) {
  21.         return null;
  22.     }
  23.     //后序遍历 左右头 使用栈逆序后变成  头左右，参考后序遍历非递归实现
  24.     Stack<String> stack = new Stack<>();
  25.     while (!posList.isEmpty()) {
  26.         stack.push(posList.poll());
  27.     }
  28.     return posb(stack);
  29. }
  31. private static Node posb(Stack<String> stack) {
  32.     String val = stack.pop();
  33.     if (val == null) {
  34.         return null;
  35.     }
  36.     Node node = new Node(Integer.valueOf(val));
  37.     node.right = posb(stack);
  38.     node.left = posb(stack);
  39.     return node;
  40. }
  1. //序列化
  2. public static Queue<String> levelSerial(Node head) {
  3.     Queue<String> ans = new LinkedList<>();
  4.     if (head == null) {
  5.         ans.add(null);
  6.     } else {
  7.         ans.add(String.valueOf(head.value));
  8.         Queue<Node> queue = new LinkedList<>();
  9.         queue.add(head);
  10.         while (!queue.isEmpty()) {
  11.             head = queue.poll(); // head 父   子
  12.             if (head.left != null) {
  13.                 ans.add(String.valueOf(head.left.value));
  14.                 queue.add(head.left);
  15.             } else {
  16.                 ans.add(null);
  17.             }
  18.             if (head.right != null) {
  19.                 ans.add(String.valueOf(head.right.value));
  20.                 queue.add(head.right);
  21.             } else {
  22.                 ans.add(null);
  23.             }
  24.         }
  25.     }
  26.     return ans;
  27. }
  29. //反序列化
  30. public static Node buildByLevelQueue(Queue<String> levelList) {
  31.     if (levelList == null || levelList.size() == 0) {
  32.         return null;
  33.     }
  34.     Node head = generateNode(levelList.poll());
  35.     Queue<Node> queue = new LinkedList<Node>();
  36.     if (head != null) {
  37.         queue.add(head);
  38.     }
  39.     Node node = null;
  40.     while (!queue.isEmpty()) {
  41.         node = queue.poll();
  42.         node.left = generateNode(levelList.poll());
  43.         node.right = generateNode(levelList.poll());
  44.         if (node.left != null) {
  45.             queue.add(node.left);
  46.         }
  47.         if (node.right != null) {
  48.             queue.add(node.right);
  49.         }
  50.     }
  51.     return head;
  52. }
  54. public static Node generateNode(String val) {
  55.     if (val == null) {
  56.         return null;
  57.     }
  58.     return new Node(Integer.valueOf(val));
  59. }

将N叉树使用二叉树编码和反编码

将多叉树的第一个孩子节点作为二叉树的左子树头结点，其他孩子依次作为第一个孩子节点的又节点 如下：②③④为多叉树中①的孩子节点，⑤⑥为多叉树中②的孩子节点（长兄为父） ① / ② / \ ⑤ ③ \ \ ⑥ ④

  1. //N叉树
  2. public static class Node {
  3.     public int val;
  4.     public List<Node> children;
  6.     public Node() {
  7.     }
  9.     public Node(int _val) {
  10.         val = _val;
  11.     }
  13.     public Node(int _val, List<Node> _children) {
  14.         val = _val;
  15.         children = _children;
  16.     }
  17. };
  19. //二叉树
  20. public static class TreeNode {
  21.     int val;
  22.     TreeNode left;
  23.     TreeNode right;
  25.     TreeNode(int x) {
  26.         val = x;
  27.     }
  28. }
  30. //将多叉树转为二叉树
  31. public TreeNode encode(Node root) {
  32.     if (root == null) {
  33.         return null;
  34.     }
  35.     TreeNode head = new TreeNode(root.val);
  36.     head.left = en(root.children);
  37.     return head;
  38. }
  39. private TreeNode en(List<Node> children) {
  40.     TreeNode head = null;
  41.     TreeNode cur = null;
  42.     for (Node child : children) {
  43.         TreeNode tNode = new TreeNode(child.val);
  44.         if (head == null) {
  45.             head = tNode;
  46.         } else {
  47.             cur.right = tNode;
  48.         }
  49.         cur = tNode;
  50.         cur.left = en(child.children);
  51.     }
  52.     return head;
  53. }
  55. //将二叉树转为多叉树
  56. public Node decode(TreeNode root) {
  57.     if (root == null) {
  58.         return null;
  59.     }
  60.     return new Node(root.val, de(root.left));
  61. }
  62. public List<Node> de(TreeNode root) {
  63.     List<Node> children = new ArrayList<>();
  64.     while (root != null) {
  65.         children.add(new Node(root.val, de(root.left)));
  66.         root = root.right;
  67.     }
  68.     return children;
  69. }

给定二叉树中的某个节点，返回该节点的后继节点

二叉树的定义如下： class Node { V value; Node left; Node right; Node parent; }

后继节点：在二叉树中序遍历中的下一个节点

  1. public static Node getSuccessorNode(Node node) {
  2.     if (node == null) {
  3.         return node;
  4.     }
  5.     if (node.right != null) {
  6.         //如果有右子树，那后继节点为右子树上最左节点
  7.         return getLeftMost(node.right);
  8.     } else { // 无右子树
  9.         //寻找该节点第一次出现在哪个父亲节点的左子树上，则该父亲节点即为此节点的后继节点
  10.         Node parent = node.parent;
  11.         while (parent != null && parent.right == node) { // 当前节点是其父亲节点右孩子
  12.             node = parent;
  13.             parent = node.parent;
  14.         }
  15.         return parent;
  16.     }
  17. }
  19. public static Node getLeftMost(Node node) {
  20.     if (node == null) {
  21.         return node;
  22.     }
  23.     while (node.left != null) {
  24.         node = node.left;
  25.     }
  26.     return node;
  27. }

如何设计一个打印正科树的打印函数

请把一张纸条竖着放在桌子上，然后从纸条的下方向上方对折1次，压出折痕后展开。此时折痕是凹下去的，即折痕凸起的方向指向纸条的背面。如果从纸条的下边向上方连续对折2吃，压出折痕后展开，此时有三条折痕，从上到下一次是下折痕、下折痕和上折痕。给定一个输入参数N，代表纸条都从下边向上方连续对折N次。请从上到下打印所有折痕的方向。例如：N=1时，打印：dwon；N=2时，打印：down down up

  1. //该题的规律，折痕最终组成一颗二叉树，折的次数代表二叉树有几层
  2. //该二叉树中，头结点是凹折痕，之后任何节点的左节点都是凹，任何节点的右节点都是凸
  3. public static void printAllFolds(int N) {
  4.     process(1, N, true);
  5.     System.out.println();
  6. }
  8. // 当前你来了一个节点，脑海中想象的！
  9. // 这个节点在第i层，一共有N层，N固定不变的
  10. // 这个节点如果是凹的话，down = T
  11. // 这个节点如果是凸的话，down = F
  12. // 函数的功能：中序打印以你想象的节点为头的整棵树！
  13. public static void process(int i, int N, boolean down) {
  14.     if (i > N) {
  15.         return;
  16.     }
  17.     process(i + 1, N, true);
  18.     System.out.print(down ? "凹 " : "凸 ");
  19.     process(i + 1, N, false);
  20. }

image.png
image.png

image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
满二叉树：高度是L，节点数是N，满足2^L-1 = N
image.png
image.png
image.png

对数器

image.pngimage.png

image.png
image.png
image.png