【14】二叉树的Morris等

一.树形dp套路

二.派对的最大快乐值

三.Morris遍历

morris先序遍历

morris中序遍历

moris后序遍历

判断是不是搜索二叉树

四.额外习题

一.树形dp套路

情况1：最大距离，节点X不参与。 => 左树最大距离 or 右树最大距离

情况2：最大距离，节点X参与。 => 最大距离 = 左树高度+1+右树高度

常见的分类，是头节点参不参与来罗列可能性。

可以设计：
节点的信息 => 最大距离maxDistance 、树高height

节点cur时的最大距离 = max{left的maxDistance, right的maxDistance，left的height+right的height+1}

	public static class Node { // 树节点public int value; // 节点值public Node left; // 左子树public Node right; // 右子树public Node(int data) { // 构造this.value = data;}}// 返回最大距离public static int maxDistance(Node head) { return process(head).maxDistance;}// 一个节点的返回信息public static class ReturnType{public int maxDistance; // 最大距离public int h; // 高度public ReturnType(int m, int h) { // 构造this.maxDistance = m;; this.h = h;}}// 给出当前节点的返回信息（最大距离，高度）public static ReturnType process(Node head) {if(head == null) {return new ReturnType(0,0);}ReturnType leftReturnType = process(head.left); // 左树返回信息ReturnType rightReturnType = process(head.right); // 右数返回信息int includeHeadDistance = leftReturnType.h + 1 + rightReturnType.h; // 计算包含根节点的最大距离int p1 = leftReturnType.maxDistance; // 左子树最大距离int p2 = rightReturnType.maxDistance; // 右子树最大举例int resultDistance = Math.max(Math.max(p1, p2), includeHeadDistance); // 到当前位置可以获得的最大距离int hitself  = Math.max(leftReturnType.h, leftReturnType.h) + 1; // 高度return new ReturnType(resultDistance, hitself); // 将信息放回给上一级}

二.派对的最大快乐值

情况1：节点X参与

X参与的最大快乐 = X乐 + a不来的最大快乐 + b不来的最大快乐 + c不来的最大快乐

情况2：节点X不参与

X不参与的最大快乐 = 0 + max(a来的最大快乐，a不来的最大快乐) + max(b来的最大快乐，b不来的最大快乐) + max(c来的最大快乐，c不来的最大快乐)

	public static class Employee{public int happy;public List<Employee> nexts;}public static class ReturnType{public int no_maxhappy;public int yes_maxhappy;public ReturnType(int no, int yes) {no_maxhappy=no;yes_maxhappy=yes;}}public static ReturnType process(Employee head) {if(head.nexts.isEmpty()) { // 基层员工 return new ReturnType(0, head.happy);}int no_maxhappy=0; // head不来的最大快乐int yes_maxhappy=head.happy; // head来的最大快乐for(Employee next:head.nexts) {ReturnType node=process(next);yes_maxhappy+=node.no_maxhappy;no_maxhappy+=Math.max(node.no_maxhappy, node.yes_maxhappy);}return new ReturnType(no_maxhappy, yes_maxhappy);}

三.Morris遍历

笔试不要用Morris遍历，面试阶段用。（学术名词：线索二叉树）

【如果不用栈，如何回到上级节点，用底层节点大量的空闲指针】

标准1：如果没有左树 => 当前节点cur向右树走。

标准2：

如果有左树，找到左树中最右节点 => 最右节点右指针为空 => 右指针指向当前节点cur => 当前节点cur向左树走。

标准3：

如果有左树，找到左树中最右节点 => 最右节点右指针不为空 => 当前节点cur向右树走。

	public static class Node {public int value;Node left;Node right;public Node(int data) {this.value = data;}}public static void morris(Node head) {if (head == null) {return;}Node cur1 = head;Node cur2 = null;while (cur1 != null) { //  过流程cur2 = cur1.left; // cur2是cur左孩子if (cur2 != null) {while (cur2.right != null && cur2.right != cur1) {cur2 = cur2.right;}// cur2变成cur左子树上，最后的节点if (cur2.right == null) { // 这是第一次来到curcur2.right = cur1;cur1 = cur1.left;continue;} else { // cur2.right == nullcur2.right = null;}}cur1 = cur1.right;}}

单独遍历左子树有边界这件事，每个节点至多被遍历1次，总代价至多是O(n)，并不会多严重。

morris先序遍历

只一次来到的节点 => 直接打印
来到两次的节点 => 第一次打印

	public static void morrisPre(Node head) {if (head == null) {return;}Node cur1 = head;Node cur2 = null;while (cur1 != null) {cur2 = cur1.left;if (cur2 != null) {while (cur2.right != null && cur2.right != cur1) {cur2 = cur2.right;}if (cur2.right == null) {cur2.right = cur1;System.out.print(cur1.value + " ");cur1 = cur1.left;continue;} else {cur2.right = null;}} else {System.out.print(cur1.value + " ");}cur1 = cur1.right;}System.out.println();}

morris中序遍历

只一次来到的节点 => 直接打印
来到两次的节点 => 第二次打印

	public static void morrisIn(Node head) {if (head == null) {return;}Node cur1 = head;Node cur2 = null;while (cur1 != null) { //  过流程cur2 = cur1.left; // cur2是cur左孩子if (cur2 != null) {while (cur2.right != null && cur2.right != cur1) {cur2 = cur2.right;}// cur2变成cur左子树上，最后的节点if (cur2.right == null) { // 这是第一次来到curcur2.right = cur1;cur1 = cur1.left;continue;} else { // cur2.right == nullcur2.right = null;}}System.out.print(cur1.value + " ");cur1 = cur1.right;}System.out.println();}

moris后序遍历

	public static void morrisPos(Node head) {if (head == null) {return;}Node cur1 = head;Node cur2 = null;while (cur1 != null) {cur2 = cur1.left;if (cur2 != null) {while (cur2.right != null && cur2.right != cur1) {cur2 = cur2.right;}if (cur2.right == null) {cur2.right = cur1;cur1 = cur1.left;continue;} else {cur2.right = null;printEdge(cur1.left);}}cur1 = cur1.right;}printEdge(head);System.out.println();}public static void printEdge(Node head) {Node tail = reverseEdge(head);Node cur = tail;while (cur != null) {System.out.print(cur.value + " ");cur = cur.right;}reverseEdge(tail);}public static Node reverseEdge(Node from) {Node pre = null;Node next = null;while (from != null) {next = from.right;from.right = pre;pre = from;from = next;}return pre;}

判断是不是搜索二叉树

在中序遍历的位置判断，是否preValue是一直在递增的。

	public static boolean isBST(Node head) {if (head == null) {return true;}Node cur1 = head;Node cur2 = null;int preValue=Integer.MIN_VALUE;while (cur1 != null) { //  过流程cur2 = cur1.left; // cur2是cur左孩子if (cur2 != null) {while (cur2.right != null && cur2.right != cur1) {cur2 = cur2.right;}// cur2变成cur左子树上，最后的节点if (cur2.right == null) { // 这是第一次来到curcur2.right = cur1;cur1 = cur1.left;continue;} else { // cur2.right == nullcur2.right = null;}}if(cur1.value <= preValue) {return false;}preValue = cur1.value;cur1 = cur1.right;}return true;}