今天主要讨论:二叉树相关内容
实现二叉树的先序、中序、后序遍历,包括递归方式和非递归方式
先序遍历 头左右,右图遍历顺序
如果打印时机放在第一次来到这个节点的时候,就是先序遍历。public static voidpreOrderRecur(Node head) {if (head == null) {return; } System.out.print(head.value+ " "); preOrderRecur(head.left); preOrderRecur(head.right); }
如果放在第二次来到这个节点的时候,就是中序遍历。public static voidinOrderRecur(Node head) {if (head == null) {return; } inOrderRecur(head.left); System.out.print(head.value+ " "); inOrderRecur(head.right); }
如果把打印时机放在第三次来点这个节点的时候,就是后序遍历。public static voidposOrderRecur(Node head) {if (head == null) {return; } posOrderRecur(head.left); posOrderRecur(head.right); System.out.print(head.value+ " "); }
主要是打印时机放在哪里。就被加工出了先序中序后序。
非递归(先序):
中间在最前面,先压right再压left
因为二叉树只能一直往下走,那就要想一个能回去的结构,栈机结构就很合适。
public static voidpreOrderUnRecur(Node head) { System.out.print("pre-order: ");if (head != null) { Stack
非递归(中序):左中右
整棵树是可以被左边界分解的(弹出顺序是左中)。逆序去处理的过程,实际上可以把整棵树都打印出来。回到2的时候,又把2的右树进行左边界分解,所以你懂得,在分解的时候也不耽误打印整棵树。
public static voidinOrderUnRecur(Node head) { System.out.print("in-order: ");if (head != null) { Stack
非递归(后序):左右中
递归会返回一个节点三次,而栈会返回两次,后序遍历需要在返回第三次的时候打印。
修改先序遍历,这次先压入左子树,形成中右左,再利用一个辅助栈,把打印结果逆序打印,即是答案。
public static voidposOrderUnRecur1(Node head) { System.out.print("pos-order: ");if (head != null) { Stack
极客写法:只使用一个栈public static voidposOrderUnRecur2(Node h) { System.out.print("pos-order: ");if (h != null) { Stack
如何直观的打印一颗二叉树
一个福利函数,用于调试二叉树。
H1H表示1是头结点,v66v是向下指的,他的父节点是左下方离他最近的
^555555^是向上指的,父节点为左上距离最近的。
public classCode02PrintBinaryTree {public static classNode {public intvalue;publicNode left;publicNode right;public Node(intdata) {this.value =data; } }public static voidprintTree(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, intlen) {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(intnum) { String space= " "; StringBuffer buf= new StringBuffer("");for (int i = 0; i < num; i++) { buf.append(space); }returnbuf.toString(); }public static voidmain(String[] args) { Node head= new Node(1); head.left= new Node(-222222222); head.right= new Node(3); head.left.left= newNode(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 classNode { public intvalue; publicNode left; publicNode right; publicNode parent; public Node(int data) { this.value =data; } }
该结构比普通二叉树节点结构多了一个指向父节点的parent指针。假设有一棵Node类型的节点组成的二叉树,树中每个节点的parent指针都正确地指向自己的父节点,头节点的parent指向null。只给一个在二叉树中的某个节点 node,请实现返回node的后继节点的函数。
在二叉树的中序遍历的序列中,node的下一个节点叫作node的后继节点。
中序遍历的顺序。(前继和后继节点)
怎么避免遍历整棵树,也能找到后继节点?
规律:x节点,如果有右子树,那么他的后继节点是右子树上最左的节点。(根据遍历顺序左中右,右子树后下一个遍历的就是左)
当x没有右子树,要找哪一个结点的左子树是以x结尾的。
通过x的父指针找到父结点,如果发现x是右孩子,就继续往上,一直到某一节点,是他父结点的左孩子,停止。(注意最右边的7找到的是null,代码层面要做相应的判断)
public classCode03SuccessorNode {public static classNode {public intvalue;publicNode left;publicNode right;publicNode parent;public Node(intdata) {this.value =data; } }public staticNode getSuccessorNode(Node node) {if (node == null) {returnnode; }if (node.right != null) {//如果有右子树 returngetLeftMost(node.right); }else {//如果没有右子树 Node parent =node.parent;while (parent != null && parent.left !=node) { node=parent; parent=node.parent; }returnparent; } }//获得最左边的节点 public staticNode getLeftMost(Node node) {if (node == null) {returnnode; }while (node.left != null) { node=node.left; }returnnode; }public static voidmain(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)); } }
前驱怎么找?
x如果有左子树,就是左子树最右的节点。
如果x没有左子树,往上找,找到一个父结点的右孩子,是当前节点就停。public staticNode getPrecursorNode(Node node){if (node == null) {returnnode; }if(node.left != null){returngetRightMost(node); }else{ Node parent=node.parent;while(parent!=null&& parent.right!=node){ node=parent; parent=node.parent; }returnparent; } }//获得最右边的节点 public staticNode getRightMost(Node node) {if (node == null) {returnnode; }while (node.right != null) { node=node.right; }returnnode; }
一般亚马逊、谷歌、微软公司,4~5面。
要达到,面试官准备给你的题库全彻底完成。
3面4面就是技术面了,比方说设计一个系统停车场系统、图书馆系统
如果题目做完,需要问问面试官还有没有题目。万无一失
介绍二叉树的序列化和反序列化
怎么把信息保存成文件形式,以确保下次可以重建一棵树。
第一种:先序的方式序列化,树怎么变字符串,/#表示遇到空
需要/#和_是因为能更好的表示一些特殊的结构。
留下划线的原因是为了识别以下的树形结构:
public staticString serialByPre(Node head) {if (head == null) {return "/#"; } String res= head.value + ""; res+=serialByPre(head.left); res+=serialByPre(head.right);returnres; }
怎么反序列化:怎么序列化的就怎么反序列化
利用_分隔,获得就是每一个节点,利用先序遍历的方式,反序列化
按照中左右的方式,依次建立。碰到空就不为空建立子树,返回父节点建立其他子树。(中序、后序同理)
public staticNode reconByPreString(String preStr) { String[] values= preStr.split("_"); Queue
OJ测试就是通过把你的二叉树序列化,再和正确答案比对来判断是否正确的。牛客网就是按照层来序列化。
按层序列化同理:
public staticString serialByLevel(Node head) {if (head == null) {return "/#"; } String res= head.value + ""; Queue
折纸问题(福利课讲的)
【题目】 请把一段纸条竖着放在桌子上,然后从纸条的下边向上方对折1次,压出折痕后展开。此时 折痕是凹下去的,即折痕突起的方向指向纸条的背面。如果从纸条的下边向上方连续对折2 次,压出折痕后展开,此时有三条折痕,从上到下依次是下折痕、下折痕和上折痕。
给定一 个输入参数N,代表纸条都从下边向上方连续对折N次,请从上到下打印所有折痕的方向。 例如:N=1时,打印: down N=2时,打印: down down up
参考:https://blog.csdn.net/zhou_209/article/details/79437262
判断一棵二叉树是否是平衡二叉树
在树中任何一个节点,它左子树和右子树的高度差不超过一,这叫平衡二叉树。抛出一个套路:递归函数很好用,可以回到一个三次。
四个信息:左/右是否平衡、左/右的高
所以经过分析每颗子树应该返回,是否平衡和树高的信息。
下面就是码代码阶段:
难度在于要列出可能性。写代码的过程高度套路化。
列出可能性、整理出返回值的类型、整个递归过程按照同样的结构、得到子树的信息、整合子树的信息、加工出我的信息、往上返回、要求结构完全一致,因为是递归函数。
public static classReturnData{public booleanisBalance;public intlevel;public ReturnData(boolean isBalance, intlevel) {this.isBalance =isBalance;this.level =level; } }public staticReturnData process(Node head){if(head == null){return new ReturnData(true,0); }//如果左子树或者右子树返回了他们不是平衡的,那总体也不会是平衡的 ReturnData lRData =process(head.left);if(!lRData.isBalance){return new ReturnData(true,0); } ReturnData rRData=process(head.right);if(!rRData.isBalance){return new ReturnData(true,0); }if(Math.abs(lRData.level - rRData.level) > 1){return new ReturnData(true,0); }return new ReturnData(true,Math.max(lRData.level,rRData.level)+1); }
你就想我们会遍历每个节点,我考虑以每个节点为头的整棵树,怎么怎么样都判断完,那么我整个答案就出来了。
这个大套路,整个方法论就这个过程。
左树收集什么信息,右树收集什么信息,列出可能性,这是你要去想的。
高度怎么变化的?
public classCode06IsBalancedTree {public static classNode { ... }public static booleanisBalance(Node head) {boolean[] res = new boolean[1]; res[0] = true; getHeight(head,1, res);return res[0]; }public static int getHeight(Node head, int level, boolean[] res) {if (head == null) {returnlevel; }int lH = getHeight(head.left, level + 1, res);if (!res[0]) {returnlevel; }int rH = getHeight(head.right, level + 1, res);if (!res[0]) {returnlevel; }if (Math.abs(lH - rH) > 1) { res[0] = false; }returnMath.max(lH, rH); }public static voidmain(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); System.out.println(isBalance(head)); } }
具体想进阶参考:树形DP
平衡二叉树用于解决效率的问题。
判断一棵树是否是搜索二叉树、判断一棵树是否是完全二叉树
搜索二叉树:左子树比他小,右子树比他大
中序遍历依次升序的就是。(通常来讲不出现重复节点,重复的话可以压缩在同一个list里面)
代码实现通过修改非递归的中序遍历来判断(对比之前的数和显示的数是否呈现出升序)(递归版怎么改?难度比较大)public static booleanisBST(Node head) {if (head == null) {return true; } Stack //Morris遍历版本//左子树小、右子树大 public static booleanisBST(Node head) {if (head == null) {return true; }boolean res = true; Node pre= null; 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; } }if (pre != null && pre.value >cur1.value) { res= false; } pre=cur1; cur1=cur1.right; }returnres; } 完全二叉树怎么判断? 按层遍历,以下条件按照顺序判断 1、如果一个子树有右孩子没左孩子肯定不是完二叉。返回false 2、如果一个节点,不是左右孩子都全,出现这种情况,他后面出现的节点,都必须是叶子节点,否则false。 State状态一开始是false,遇到二的情况变true,遇到后续节点不是叶子节点就直接返回false 节点5中了第二种情况,接下来的都要是叶子节点。 public static booleanisCBT(Node head) {if (head == null) {return true; } Queue DQ和Q都可以使用双端链表来实现。(Java中的LinkedList底层实现) 已知一棵完全二叉树,求其节点的个数 要求:时间复杂度低于O(N),N为这棵树的节点个数 先遍历左边界,获得层高。然后遍历右子树的左边界,如果等于总的左边界的层高,就证明,左子树是满二叉树。 然后通过公式计算出左子树的个数,再递归处理右子树。 如果右子树的左边界没到最后一层。那就证明,右子树是左树高度-1的满二叉树。然后再递归处理左树。 所以每次拿到一个节点,就判断右树的左边界是否到最后一层,到了左树就是满的,没到右树就是满的,只不过左树和右树满的高度不一样而已,都可以使用公式来计算。剩下的节点递归去求。 代码解说: 算法复杂度: 遍历节点 logN 获得左边界 LogN LogN² 题目八
public classCode08CompleteTreeNodeNumber {public static classNode { ... }public static intnodeNum(Node head) {if (head == null) {return 0; }return bs(head, 1, mostLeftLevel(head, 1)); }//当前节点、节点在第几层、整棵树的树高 public static int bs(Node node, int level, inth) {if (level == h) {//如果level来到最后一层,就是叶子节点 return 1; }if (mostLeftLevel(node.right, level + 1) ==h) {return (1 << (h - level)) + bs(node.right, level + 1, h); }else{return (1 << (h - level - 1)) + bs(node.left, level + 1, h); } }public static int mostLeftLevel(Node node, intlevel) {while (node != null) { level++; node=node.left; }return level - 1; }public static voidmain(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); System.out.println(nodeNum(head)); } }