二叉树结构描述

public static class Node {public int value;public Node left;public Node right;public Node(int v) {value = v;}}

递归方式实现二叉树的先序、中序、后序遍历：

1. 理解递归序，递归遍历的本质是递归序，二叉树递归序，每个节点都会达到三次。
2. 先序、中序、后序都可以在递归序的基础上加工出来
3. 第一次到达一个节点就打印就是先序、第二次打印即中序、第三次即后序

package com.harrison.seven;public class Code01_RecursiveTraversalBT {public static class Node {public int value;public Node left;public Node right;public Node(int v) {value = v;}}// 先序打印所有节点public static void pre(Node head) {if (head == null) {return;}System.out.println(head.value);pre(head.left);pre(head.right);}// 中序打印所有节点public static void in(Node head) {if (head == null) {return;}in(head.left);System.out.println(head.value);in(head.right);}// 后序打印所有节点public static void pos(Node head) {if (head == null) {return;}pos(head.left);pos(head.right);System.out.println(head.value);}public static void f(Node head) {if (head == null) {return;}f(head.left);f(head.right);}public static void main(String[] args) {Node head = new Node(1);head.left = new Node(2);head.right = new Node(3);head.left.left = new Node(4);head.left.right = new Node(5);head.right.left = new Node(6);head.right.right = new Node(7);pre(head);System.out.println("========");in(head);System.out.println("========");pos(head);System.out.println("========");}
}

非递归方式实现二叉树的先序、中序、后序遍历：

1. 任何递归函数都可以改成非递归
2. 自己设计压栈的来实现

package com.harrison.seven;import java.util.Stack;public class Code02_UnRecursiveTraversalBT {public static class Node {public int value;public Node left;public Node right;public Node(int v) {value = v;}}// 非递归方式先序遍历二叉树/*** 弹出就打印 如果有右孩子，先压入右孩子 如果有左孩子，压入左孩子* * @param head*/public static void pre(Node head) {System.out.print("pre-order：");if (head != null) {Stack<Node> stack = new Stack<Node>();stack.add(head);while (!stack.isEmpty()) {head = stack.pop();System.out.print(head.value+" ");if (head.right != null) {stack.push(head.right);}if (head.left != null) {stack.push(head.left);}}}}// 非递归方式中序遍历二叉树/*** 1)整条左边界依次入栈 2)条件1)不满足时，弹出打印，在右树上执行条件1)* * @param cur*/public static void in(Node cur) {System.out.print("in-order：");if (cur != null) {Stack<Node> stack = new Stack<Node>();while (!stack.isEmpty() || cur != null) {if (cur != null) {stack.push(cur);cur = cur.left;} else {cur = stack.pop();System.out.print(cur.value + " ");cur = cur.right;}}}System.out.println();}// 非递归方式后序遍历二叉树/*** 弹打印 如有左，压入左 如有右，压入右*/public static void pos1(Node head) {System.out.print("pos-order：");if (head != null) {Stack<Node> s1 = new Stack<Node>();Stack<Node> s2 = new Stack<Node>();s1.push(head);while (!s1.isEmpty()) {head = s1.pop();// 头 右 左s2.push(head);if (head.left != null) {s1.push(head.left);}if (head.right != null) {s1.push(head.right);}}// 左 右 头while (!s2.isEmpty()) {System.out.print(s2.pop().value + " ");}}}// 非递归方式实现后序遍历，只用一个栈public static void pos2(Node h) {System.out.print("pos-order：");if (h != null) {Stack<Node> stack = new Stack<Node>();stack.push(h);Node c = null;while (!stack.isEmpty()) {c = stack.peek();if (c.left != null && h != c.left && h != c.right) {stack.push(c.left);} else if (c.right != null && h != c.right) {stack.push(c.right);} else {System.out.print(stack.pop().value + " ");h = c;}}}System.out.println();}public static void main(String[] args) {Node head = new Node(1);head.left = new Node(2);head.right = new Node(3);head.left.left = new Node(4);head.left.right = new Node(5);head.right.left = new Node(6);head.right.right = new Node(7);pre(head);System.out.println("\n========");in(head);System.out.println("========");pos1(head);System.out.println("\n========");pos2(head);}
}

实现二叉树的按层遍历

1. 其实就是宽度优先遍历，用队列
2. 可以通过设置flag变量的方式，来发现某一层的结束（看题目）

package com.harrison.seven;import java.util.LinkedList;
import java.util.Queue;public class Code03_LevelTraversalBT {public static class Node{public int value;public Node left;public Node right;public Node(int v) {value=v;}}//实现二叉树的按层遍历，其实就是宽度优先遍历，用队列public static void level(Node head) {if(head==null) {return ;}Queue<Node> queue=new LinkedList<>();queue.add(head);while(!queue.isEmpty()) {Node cur=queue.poll();System.out.print(cur.value+" ");if(cur.left!=null) {queue.add(cur.left);}if(cur.right!=null) {queue.add(cur.right);}}}public static void main(String[] args) {Node head = new Node(1);head.left = new Node(2);head.right = new Node(3);head.left.left = new Node(4);head.left.right = new Node(5);head.right.left = new Node(6);head.right.right = new Node(7);level(head);System.out.println("\n========");}
}

树的最大宽度：求二叉树最宽的层有多少个结点

package com.harrison.seven;import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;public class Code04_TreeMaxWidth {public static class Node {public int value;public Node left;public Node right;public Node(int v) {value = v;}}public static int maxWidthUseMap(Node head) {if (head == null) {return 0;}Queue<Node> queue = new LinkedList<>();queue.add(head);// key 在哪一层 value 结点值HashMap<Node, Integer> levelMap = new HashMap<>();levelMap.put(head, 1);int curLevel = 1;// 当前正在统计哪一层的宽度int curLevelNodes = 0;// 当前层目前的宽度，进来的时候不统计，出去的时候再统计int max = 0;while (!queue.isEmpty()) {Node cur = queue.poll();int curNodeLevel = levelMap.get(cur);if (cur.left != null) {levelMap.put(cur.left, curNodeLevel+1);queue.add(cur.left);}if (cur.right != null) {levelMap.put(cur.right, curNodeLevel+1);queue.add(cur.right);}if (curNodeLevel == curLevel) {curLevelNodes++;} else {max = Math.max(max, curLevelNodes);curLevel++;curLevelNodes = 1;}}max = Math.max(max, curLevelNodes);return max;}public static int maxWidthNoMap(Node head) {if (head == null) {return 0;}Queue<Node> queue = new LinkedList<>();queue.add(head);Node curEnd = head;// 当前层的最右结点Node nextEnd = null;// 下一层的最右结点int max = 0;int curLevelNodes = 0;// 当前层的结点数while (!queue.isEmpty()) {Node cur = queue.poll();if (cur.left != null) {queue.add(cur.left);nextEnd = cur.left;}if (cur.right != null) {queue.add(cur.right);nextEnd = cur.right;}curLevelNodes++;if (cur == curEnd) {max = Math.max(max, curLevelNodes);curLevelNodes = 0;curEnd = nextEnd;}}return max;}// for testpublic static Node generateRandomBST(int maxLevel, int maxValue) {return generate(1, maxLevel, maxValue);}// for testpublic static Node generate(int level, int maxLevel, int maxValue) {if (level > maxLevel || Math.random() < 0.5) {return null;}Node head = new Node((int) (Math.random() * maxValue));head.left = generate(level + 1, maxLevel, maxValue);head.right = generate(level + 1, maxLevel, maxValue);return head;}public static void main(String[] args) {int maxLevel = 10;int maxValue = 100;int testTimes = 1000000;for (int i = 0; i < testTimes; i++) {Node head = generateRandomBST(maxLevel, maxValue);if (maxWidthUseMap(head) != maxWidthNoMap(head)) {System.out.println("Oops!");}}System.out.println("finish!");}
}

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

1. 可以用先序或者中序或者后序或者按层遍历，来实现二叉树的序列化
2. 用了什么方式序列化，就用什么样的方式反序列化

按层序列化

package com.harrison.seven;import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;public class Code05_SerializeAndReconstructTree {public static class Node {public int value;public Node left;public Node right;public Node(int v) {value = v;}}// 先序方式序列化二叉树public static Queue<String> preSerial(Node head) {Queue<String> ans = new LinkedList<>();pres(head, ans);return ans;}public static void pres(Node head, Queue<String> ans) {if (head == null) {ans.add(null);} else {ans.add(String.valueOf(head.value));pres(head.left, ans);pres(head.right, ans);}}// 中序方式序列化二叉树public static Queue<String> inSerial(Node head) {Queue<String> ans = new LinkedList<>();ins(head, ans);return ans;}public static void ins(Node head, Queue<String> ans) {if (head == null) {ans.add(null);} else {ins(head.left, ans);ans.add(String.valueOf(head.value));ins(head.right, ans);}}// 后序方式序列化二叉树public static Queue<String> posSerial(Node head) {Queue<String> ans = new LinkedList<>();poss(head, ans);return ans;}public static void poss(Node head, Queue<String> ans) {if (head == null) {ans.add(null);} else {poss(head.left, ans);poss(head.right, ans);ans.add(String.valueOf(head.value));}}// 先序方式重建二叉树public static Node buildByPreQueue(Queue<String> prelist) {if (prelist == null || prelist.size() == 0) {return null;}return preb(prelist);}public static Node preb(Queue<String> prelist) {String value = prelist.poll();if (value == null) {return null;}Node head = new Node(Integer.valueOf(value));head.left = preb(prelist);head.right = preb(prelist);return head;}// 后序方式重建二叉树public static Node buildByPosQueue(Queue<String> poslist) {if (poslist == null || poslist.size() == 0) {return null;}Stack<String> stack = new Stack<>();while (!poslist.isEmpty()) {stack.push(poslist.poll());}return posb(stack);}public static Node posb(Stack<String> posstack) {String value = posstack.pop();if (value == null) {return null;}Node head = new Node(Integer.valueOf(value));head.right = posb(posstack);head.left = posb(posstack);//为啥先右后左？？？return head;}public static Node generateNode(String val) {if (val == null) {return null;}return new Node(Integer.valueOf(val));}// 按层序列化二叉树，并不是通过递归实现的public static Queue<String> levelSerial(Node head) {Queue<String> ans = new LinkedList<>();if (head == null) {ans.add(null);} else {ans.add(String.valueOf(head.value));Queue<Node> queue = new LinkedList<Node>();queue.add(head);while (!queue.isEmpty()) {head = queue.poll();if (head.left != null) {ans.add(String.valueOf(head.left.value));queue.add(head.left);} else {ans.add(null);}if (head.right != null) {ans.add(String.valueOf(head.right.value));queue.add(head.right);} else {ans.add(null);}}}return ans;}// 反序列化public static Node buildByLevelQueue(Queue<String> levelList) {if (levelList == null || levelList.size() == 0) {return null;}Node head = generateNode(levelList.poll());Queue<Node> queue = new LinkedList<Node>();if (head != null) {queue.add(head);}Node node = null;while (!queue.isEmpty()) {node = queue.poll();node.left = generateNode(levelList.poll());node.right = generateNode(levelList.poll());if (node.left != null) {queue.add(node.left);}if (node.right != null) {queue.add(node.right);}}return head;}public static Node generate(int level, int maxLevel, int maxValue) {if (level > maxLevel || Math.random() < 0.5) {return null;}Node head = new Node((int) (Math.random() * maxValue));head.left = generate(level + 1, maxLevel, maxValue);head.right = generate(level + 1, maxLevel, maxValue);return head;}public static Node generateRandomBST(int maxLevel, int maxValue) {return generate(1, maxLevel, maxValue);}public static boolean isSameValueStructure(Node head1, Node head2) {if (head1 == null && head2 != null) {return false;}if (head1 != null && head2 == null) {return false;}if (head1 == null && head2 == null) {return true;}if (head1.value != head2.value) {return false;}return isSameValueStructure(head1.left, head2.left) && isSameValueStructure(head1.right, head2.right);}public static void printTree(Node head) {System.out.println("Binary Tree:");printInOrder(head, 0, "H", 17);System.out.println();}public static void printInOrder(Node head, int height, String to, int len) {if (head == null) {return;}printInOrder(head.right, height + 1, "v", len);String val = to + head.value + to;int lenM = val.length();int lenL = (len - lenM) / 2;int lenR = len - lenM - lenL;val = getSpace(lenL) + val + getSpace(lenR);System.out.println(getSpace(height * len) + val);printInOrder(head.left, height + 1, "^", len);}public static String getSpace(int num) {String space = " ";StringBuffer buf = new StringBuffer("");for (int i = 0; i < num; i++) {buf.append(space);}return buf.toString();}public static void main(String[] args) {int maxLevel = 5;int maxValue = 100;int testTimes = 1000000;System.out.println("test begin");for (int i = 0; i < testTimes; i++) {Node head = generateRandomBST(maxLevel, maxValue);Queue<String> pre = preSerial(head);Queue<String> pos = posSerial(head);Queue<String> level = levelSerial(head);Node preBuild = buildByPreQueue(pre);Node posBuild = buildByPosQueue(pos);Node levelBuild = buildByLevelQueue(level);if (!isSameValueStructure(preBuild, posBuild) || !isSameValueStructure(posBuild, levelBuild)) {System.out.println("Oops!");}}System.out.println("test finish!");}
}

如何设计一个打印整棵树的打印函数

package com.harrison.seven;public class Code06_PrintBinaryTree {public static class Node {public int value;public Node left;public Node right;public Node(int data) {this.value = data;}}public static String getSpace(int num) {String space = " ";StringBuffer buf = new StringBuffer("");for (int i = 0; i < num; i++) {buf.append(space);}return buf.toString();}public static void printInOrder(Node head, int height, String to, int len) {if (head == null) {return;}printInOrder(head.right, height + 1, "v", len);String val = to + head.value + to;int lenM = val.length();int lenL = (len - lenM) / 2;int lenR = len - lenM - lenL;val = getSpace(lenL) + val + getSpace(lenR);System.out.println(getSpace(height * len) + val);printInOrder(head.left, height + 1, "^", len);}public static void printTree(Node head) {System.out.println("Binary Tree：");printInOrder(head, 0, "H", 17);System.out.println();}public static void main(String[] args) {Node head = new Node(1);head.left = new Node(-222222222);head.right = new Node(3);head.left.left = new Node(Integer.MIN_VALUE);head.right.left = new Node(55555555);head.right.right = new Node(66);head.left.left.right = new Node(777);printTree(head);head = new Node(1);head.left = new Node(2);head.right = new Node(3);head.left.left = new Node(4);head.right.left = new Node(5);head.right.right = new Node(6);head.left.left.right = new Node(7);printTree(head);head = new Node(1);head.left = new Node(1);head.right = new Node(1);head.left.left = new Node(1);head.right.left = new Node(1);head.right.right = new Node(1);head.left.left.right = new Node(1);printTree(head);}
}

给你二叉树中的某个结点，返回该结点的后继结点

二叉树结构定义如下：

public static class Node {public int value;public Node left;public Node right;public Node parent;public Node(int data) {this.value = data;}}

后继结点：在一棵二叉树中，在中序遍历中，一个结点的下一个结点是谁！

结论（x结点的后继节点）：某一个结点（用?代替）的整颗左树上的最右结点是x，则？就是x的后继结点，但是整棵树的最右结点没有后继。

前驱结点：后继对应的就是前驱，如果一棵树有左树的话，它左树上最右的结点就是它前驱

package com.harrison.seven;public class Code07_SuccessorNode {public static class Node {public int value;public Node left;public Node right;public Node parent;public Node(int data) {this.value = data;}}// 如果有右树，则在右树上找到最左边的结点// 后继结点就是右树上最左边的结点public static Node getLeftMost(Node node) {if (node == null) {return node;}while (node.left != null) {node = node.left;}return node;}public static Node getSuccessorNode(Node node) {if (node == null) {return node;}if (node.right != null) {return getLeftMost(node.right);} else {// 没有右子树Node parent = node.parent;while (parent != null && parent.right == node) {// 当前结点是父结点的右孩子node = parent;parent = node.parent;}return parent;}}public static void main(String[] args) {Node head = new Node(6);head.parent = null;head.left = new Node(3);head.left.parent = head;head.left.left = new Node(1);head.left.left.parent = head.left;head.left.left.right = new Node(2);head.left.left.right.parent = head.left.left;head.left.right = new Node(4);head.left.right.parent = head.left;head.left.right.right = new Node(5);head.left.right.right.parent = head.left.right;head.right = new Node(9);head.right.parent = head;head.right.left = new Node(8);head.right.left.parent = head.right;head.right.left.left = new Node(7);head.right.left.left.parent = head.right.left;head.right.right = new Node(10);head.right.right.parent = head.right;Node test = head.left.left;System.out.println(test.value + " next: " + getSuccessorNode(test).value);test = head.left.left.right;System.out.println(test.value + " next: " + getSuccessorNode(test).value);test = head.left;System.out.println(test.value + " next: " + getSuccessorNode(test).value);test = head.left.right;System.out.println(test.value + " next: " + getSuccessorNode(test).value);test = head.left.right.right;System.out.println(test.value + " next: " + getSuccessorNode(test).value);test = head;System.out.println(test.value + " next: " + getSuccessorNode(test).value);test = head.right.left.left;System.out.println(test.value + " next: " + getSuccessorNode(test).value);test = head.right.left;System.out.println(test.value + " next: " + getSuccessorNode(test).value);test = head.right;System.out.println(test.value + " next: " + getSuccessorNode(test).value);test = head.right.right; // 10's next is nullSystem.out.println(test.value + " next: " + getSuccessorNode(test));}
}

折纸问题

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

package com.harrison.seven;public class Code08_PaperFolding {// 凹 down==true   凸 up==falsepublic static void process(int i,int N,boolean down) {if(i>N) {return;}process(i+1,N,true);System.out.print(down?"凹":"凸");process(i+1,N,false);}public static void printAllFolds(int N) {process(1,N,true);System.out.println();}public static void main(String[] args) {int N=4;printAllFolds(N);}
}