- [1 二叉树基本算法](#1)
  * [1.1 二叉树的遍历](#11)
    + [1.1.1 二叉树节点定义](#111)
    + [1.1.2 递归实现先序中序后序遍历](#112)
    + [1.1.3 非递归实现先序中序后序遍历(DFS)](#113)
    + [1.1.4 二叉树按层遍历(BFS)](#114)
  * [1.2 二叉树的序列化和反序列化](#12)
  * [1.3 直观打印一颗二叉树](#13)
  * [1.4 题目实战](#14)
    + [1.4.1 题目一：返回二叉树的后继节点](#141)
    + [1.4.2 题目二：折纸问题](#142)

<h1 id='1'>1 二叉树基本算法</h1>

<h2 id='11'>1.1 二叉树的遍历</h2>

<h3 id='111'>1.1.1 二叉树节点定义</h3>

```Java
    Class Node{
        // 节点的值类型
        V value;
        // 二叉树的左孩子指针
        Node left;
        // 二叉树的右孩子指针
        Node right;
    }
```

<h3 id='112'>1.1.2 递归实现先序中序后序遍历</h3>

> 先序：任何子树的处理顺序都是，先头结点，再左子树，再右子树。先处理头结点

> 中序：任何子树的处理顺序都是，先左子树，再头结点，再右子树。中间处理头结点

> 后序：任何子树的处理顺序都是，先左子树，再右子树，再头结点。最后处理头结点

对于下面的一棵树：

```
graph TD
1-->2
1-->3
2-->4
2-->5
3-->6
3-->7
```

1、 先序遍历为：1 2 4 5 3 6 7

2、 中序遍历为：4 2 5 1 6 3 7

3、 后序遍历为：4 5 2 6 7 3 1

```Java
package class07;

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 f(Node head) {
		if (head == null) {
			return;
		}
		// 1 此处打印等于先序
		f(head.left);
		// 2 此处打印等于中序
		f(head.right);
		// 3 此处打印等于后序
	}

	// 先序打印所有节点
	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 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("========");

	}

}
```

> 结论：对于树的递归，每个节点实质上会到达三次，例如上文的树结构，对于f函数，我们传入头结点，再调用左树再调用右树。实质上经过的路径为1 2 4 4 4 2 5 5 5 2 1 3 6 6 6 3 7 7 7 3 1。我们在每个节点三次返回的基础上，第一次到达该节点就打印，就是先序，第二次到达该节点打印就是中序，第三次到达该节点就是后序。

> 所以先序中序后序，只是我们的递归顺序加工出来的结果！

<h3 id='113'>1.1.3 非递归实现先序中序后序遍历(DFS)</h3>

> 思路：由于任何递归可以改为非递归，我们可以使用压栈来实现,实质就是深度优先遍历（DFS）。用先序实现的步骤，其他类似：

> 步骤一，把节点压入栈中，弹出就打印

> 步骤二，如果有右孩子先压入右孩子

> 步骤三，如果有左孩子压入左孩子

```Java
package class07;

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;
		}
	}

        // 非递归先序
	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);
				}
			}
		}
		System.out.println();
	}

        // 非递归中序
	public static void in(Node head) {
		System.out.print("in-order: ");
		if (head != null) {
			Stack<Node> stack = new Stack<Node>();
			while (!stack.isEmpty() || head != null) {
			  // 整条左边界依次入栈
				if (head != null) {
					stack.push(head);
					head = head.left;
				// 左边界到头弹出一个打印，来到该节点右节点，再把该节点的左树以此进栈
				} else {
					head = stack.pop();
					System.out.print(head.value + " ");
					head = head.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 + " ");
			}
		}
		System.out.println();
	}

        // 非递归后序2：用一个栈实现后序遍历，比较有技巧
	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("========");
		in(head);
		System.out.println("========");
		pos1(head);
		System.out.println("========");
		pos2(head);
		System.out.println("========");
	}

}

```

<h3 id='114'>1.1.4 二叉树按层遍历(BFS)</h3>

1、 其实就是宽度优先遍历(BFS)，用队列

2、 可以通过设置flag变量的方式，来发现某一层的结束

> 按层打印输出二叉树

```Java
package class07;

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.println(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("========");
	}

}

```

> 找到二叉树的最大宽度

```Java
package class07;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;

public class Code06_TreeMaxWidth {

	public static class Node {
		public int value;
		public Node left;
		public Node right;

		public Node(int data) {
			this.value = data;
		}
	}

        // 方法1使用map
	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<>();
		// head在第一层
		levelMap.put(head, 1);
		// 当前你正在统计哪一层的宽度
		int curLevel = 1; 
		// 当前层curLevel层，宽度目前是多少
		int curLevelNodes = 0; 
		// 用来保存所有层的最大值，也就是最大宽度
		int max = 0;
		while (!queue.isEmpty()) {
			Node cur = queue.poll();
			int curNodeLevel = levelMap.get(cur);
			// 当前节点的左孩子不为空，队列加入左孩子，层数在之前层上加1
			if (cur.left != null) {
				levelMap.put(cur.left, curNodeLevel + 1);
				queue.add(cur.left);
			}
			// 当前节点的右孩子不为空，队列加入右孩子，层数也变为当前节点的层数加1
			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++;
				// 结算后，当前层节点数设置为1
				curLevelNodes = 1;
			}
		}
		// 由于最后一层，没有新的一层去结算，所以这里单独结算最后一层
		max = Math.max(max, curLevelNodes);
		return max;
	}

        // 方法2不使用map
	public static int maxWidthNoMap(Node head) {
		if (head == null) {
			return 0;
		}
		Queue<Node> queue = new LinkedList<>();
		queue.add(head);
		// 当前层，最右节点是谁，初始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进行比较，计算当前最大的max
				max = Math.max(max, curLevelNodes);
				// 即将进入下一层，重置下一层节点为0个节点
				curLevelNodes = 0;
				// 当前层的最右，直接更新为找出来的下一层最右
				curEnd = nextEnd;
			}
		}
		return max;
	}

	// for test
	public static Node generateRandomBST(int maxLevel, int maxValue) {
		return generate(1, maxLevel, maxValue);
	}

	// for test
	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 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!");

	}

}
```

<h2 id='12'>1.2 二叉树的序列化和反序列化</h2>

1、 可以用先序或者中序或者后序或者按层遍历，来实现二叉树的序列化

2、 用了什么方式的序列化，就用什么方式的反序列化


> 由于如果树上的节点值相同，那么序列化看不出来该树的结构，所以我们的序列化要加上空间结构的标识，空节点补全的方式。

```Java
package class07;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class Code04_SerializeAndReconstructTree {
    /*
     * 二叉树可以通过先序、后序或者按层遍历的方式序列化和反序列化，
     * 以下代码全部实现了。
     * 但是，二叉树无法通过中序遍历的方式实现序列化和反序列化
     * 因为不同的两棵树，可能得到同样的中序序列，即便补了空位置也可能一样。
     * 比如如下两棵树
     *         __2
     *        /
     *       1
     *       和
     *       1__
     *          \
     *           2
     * 补足空位置的中序遍历结果都是{ null, 1, null, 2, null}
     *       
     * */
	public static class Node {
		public int value;
		public Node left;
		public Node right;

		public Node(int data) {
			this.value = data;
		}
	}

        // 先序序列化
	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(中右左)
		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 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 generateNode(String val) {
		if (val == null) {
			return null;
		}
		return new Node(Integer.valueOf(val));
	}

	// for test
	public static Node generateRandomBST(int maxLevel, int maxValue) {
		return generate(1, maxLevel, maxValue);
	}

	// for test
	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;
	}

	// for test
	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);
	}

	// for test
	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!");
		
	}
}
```

<h2 id='13'>1.3 直观打印一颗二叉树</h2>

> 如何设计一个打印整颗数的打印函数,简单起见，我们躺着打印，正常的树我们顺时针旋转90°即可

```Java
package class07;

public class Code05_PrintBinaryTree {

	public static class Node {
		public int value;
		public Node left;
		public Node right;

		public Node(int data) {
			this.value = data;
		}
	}

	public static void printTree(Node head) {
		System.out.println("Binary Tree:");
		// 打印函数，先传入头结点
		printInOrder(head, 0, "H", 17);
		System.out.println();
	}

    // head表示当前传入节点
    // height当前节点所在的高度
    // to表示当前节点的指向信息
    // len表示打印当前值填充到多少位当成一个完整的值
	public static void printInOrder(Node head, int height, String to, int len) {
		if (head == null) {
			return;
		}
		// 递归右树，右树向下指
		printInOrder(head.right, height + 1, "v", len);
		/**
		* 打印自己的值
		* val 表示值内容
		**/
		String val = to + head.value + to;
		int lenM = val.length();
		// 按照len算该值左侧需要填充多少空格
		int lenL = (len - lenM) / 2;
		// 按照len算该值右侧需要填充多少空格
		int lenR = len - lenM - lenL;
		// 实际值加上左右占位，表示每个值包括占位之后大小
		val = getSpace(lenL) + val + getSpace(lenR);
		System.out.println(getSpace(height * len) + val);
		// 递归左树，左树向上指
		printInOrder(head.left, height + 1, "^", len);
	}

    // 根据height*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) {
		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);

	}

}

```

<h2 id='14'>1.4 题目实战</h2>

<h3 id='141'>1.4.1 题目一：返回二叉树的后继节点</h3>

题目描述：二叉树的结构定义如下：

```Java
Class Node {
    V value;
    Node left;
    Node right;
    // 指向父亲节点
    Node parent;
}
```

给你二叉树中的某个节点，返回该节点的后继节点。后继节点表示一颗二叉树中，在中序遍历的序列中，一个个节点的下一个节点是谁。

> 方法一，通常解法思路：由于我们的节点有指向父节点的指针，而整颗二叉树的头结点的父节点为null。那么我们可以找到整棵树的头结点，然后中序遍历，再找到给定节点的下一个节点，就是该节点的后续节点。


> 方法二，考虑一个节点和其后继节点的结构之间的关系：

> 如果一个节点x有右树，那么其后继节点就是右树最左的节点。

> 如果x没有右树，往上找父亲节点。如果x是其父亲的右孩子继续往上找，如果某节点是其父亲节点的左孩子，那么该节点的父亲就是x的后继节点

> 即如果某节点左树的最右节点是x，那么该节点是x的后继

> 如果找父节点，一直找到null都不满足，那么该节点是整棵树的最右节点，没有后继

```Java
package class07;

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 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 Node getLeftMost(Node node) {
		if (node == null) {
			return node;
		}
		while (node.left != null) {
			node = node.left;
		}
		return node;
	}

	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 null
		System.out.println(test.value + " next: " + getSuccessorNode(test));
	}

}
```

> 后继节点对应的是前驱结点，前驱结点的含义是中序遍历，某节点的前一个节点

<h3 id='142'>1.4.2 题目二：折纸问题</h3>

请把一段纸条竖着放在桌子上，然后从纸条的下边向上方对折1次，压出折痕后展开。

此时折痕是凹下去的，即折痕凸起的方向指向纸条的背面。

如果从纸条的下边向上方对折2次，压出折痕后展开，此时有三条折痕，从上到下依次是下折痕，下折痕和上折痕。

给定一个输入参数N,代表纸条都从下边向上方连续对折N次。请从上到下打印所有的折痕的方向。

例如：N=1时，打印: down 。N=2时，打印：down down up

> 规律，大于一次后，每次折痕出现的位置都是在上次折痕的上方出现凹折痕，下方出现凸折痕。所以我们没必要构建这颗树，就可以用递归思维解决

```text
对应的树结构按层输出为：
            1凹
    2凹             2凸
3凹     3凸     3凹     3凸
```

```Java
package class07;

public class Code08_PaperFolding {

	public static void printAllFolds(int N) {
	    // 先从头结点出发，i初始值为1，切第一次的头结点折痕为凹折痕
		printProcess(1, N, true);
	}

	// 递归过程，来到了某一个节点，
	// i是节点的层数，N一共的层数，down == true  凹    down == false 凸
	public static void printProcess(int i, int N, boolean down) {
		if (i > N) {
			return;
		}
		// 每个当前节点的左子节点是凹
		printProcess(i + 1, N, true);
		System.out.println(down ? "凹 " : "凸 ");
		// 每个当前节点的右子树是凸
		printProcess(i + 1, N, false);
	}

	public static void main(String[] args) {
		int N = 3;
		// 折N次，打印所有凹凸分布情况
		printAllFolds(N);
	}
}
```