?？途W(wǎng) 算法入門篇 左程云老師 個(gè)人復(fù)習(xí)，如果侵全，設(shè)為私密

二叉樹遍歷（遞歸）

• 先序遍歷（中，左，右）

• 中序遍歷（左，中，右）

• 后序遍歷（左，右，中）

• 如上圖所示結(jié)構(gòu)，二叉樹的遍歷本質(zhì)上都是遞歸序，1、2和3節(jié)點(diǎn)每個(gè)都會(huì)出現(xiàn)三次，比如從節(jié)點(diǎn)1出發(fā)，來(lái)到節(jié)點(diǎn)2，節(jié)點(diǎn)2的左邊為空，返回，打印2，右邊為空，返回打印2，再返回到節(jié)點(diǎn)1，節(jié)點(diǎn)3類似。所以最后輸出的序列為1，2，2，2，1，3，3，3，1。
• 如果打印遞歸序出現(xiàn)的第1次的元素，就是先序遍歷
• 如果打印遞歸序出現(xiàn)的第2次的元素，就是中序遍歷
• 如果打印遞歸序出現(xiàn)的第3次的元素，就是后序遍歷

二叉樹遍歷（非遞歸）

先序遍歷

• 二叉樹的結(jié)構(gòu)如圖所示，準(zhǔn)備一個(gè)棧用于接收數(shù)據(jù)
• 原則只有兩點(diǎn)：1，棧中彈出節(jié)點(diǎn)叫做cur（當(dāng)前節(jié)點(diǎn)），彈出就打印；2，先打印cur的右節(jié)點(diǎn)，仔打印左節(jié)點(diǎn)，沒有就無(wú)需操作。?？站屯Ｖ?。
• 1進(jìn)棧，彈出1，打印1；將3和2壓入棧中，彈出2，打印2，將2的孩子節(jié)點(diǎn)4和5押入棧中；因?yàn)橄妊喝胗?#xff0c;再壓左，因此先將5押入，再押入4；彈出4，打印4；如上所述，先序遍歷為1，2，4，5，3，6，7

代碼

package class05;import java.util.Stack;public class Code01_PreInPosTraversal {public static class Node {public int value;public Node left;public Node right;public Node(int data) {this.value = data;}}public static void f(Node head) {// 1if (head == null) {return;}// 1f(head.left); //2//2f(head.right);// 3// 3}public static void preOrderRecur(Node head) {if (head == null) {return;}System.out.print(head.value + " ");preOrderRecur(head.left); preOrderRecur(head.right);}public static void inOrderRecur(Node head) {if (head == null) {return;}inOrderRecur(head.left);System.out.print(head.value + " ");inOrderRecur(head.right);}public static void posOrderRecur(Node head) {if (head == null) {return;}posOrderRecur(head.left);posOrderRecur(head.right);System.out.print(head.value + " ");}public static void preOrderUnRecur(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 inOrderUnRecur(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 posOrderUnRecur1(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();}public static void posOrderUnRecur2(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(5);head.left = new Node(3);head.right = new Node(8);head.left.left = new Node(2);head.left.right = new Node(4);head.left.left.left = new Node(1);head.right.left = new Node(7);head.right.left.left = new Node(6);head.right.right = new Node(10);head.right.right.left = new Node(9);head.right.right.right = new Node(11);// recursiveSystem.out.println("==============recursive==============");System.out.print("pre-order: ");preOrderRecur(head);System.out.println();System.out.print("in-order: ");inOrderRecur(head);System.out.println();System.out.print("pos-order: ");posOrderRecur(head);System.out.println();// unrecursiveSystem.out.println("============unrecursive=============");preOrderUnRecur(head);inOrderUnRecur(head);posOrderUnRecur1(head);posOrderUnRecur2(head);}}

中序遍歷（非遞歸）

• 原則只有兩點(diǎn)：1，棧中彈出節(jié)點(diǎn)叫做cur（當(dāng)前節(jié)點(diǎn)），彈出就打印；2，先打印cur的左節(jié)點(diǎn)，仔打印右節(jié)點(diǎn)，沒有就無(wú)需操作。棧空就停止。
• 不斷將右節(jié)點(diǎn)分成左和中節(jié)點(diǎn)

后序遍歷（非遞歸）

• 原則只有兩點(diǎn)：1，棧中彈出節(jié)點(diǎn)叫做cur（當(dāng)前節(jié)點(diǎn)），彈出不打印，放到一個(gè)新的棧中；2，最后將第二個(gè)棧中的元素打印，相當(dāng)于是（左，右，中），即后序遍歷

直觀打印二叉樹

package class05;public class Code02_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();}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) {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);}}

求二叉樹的最大寬度

使用隊(duì)列

• 使用一個(gè)隊(duì)列，從頭部進(jìn)入，從尾巴出來(lái)；
• 原則：彈出當(dāng)前節(jié)點(diǎn)cur，彈出并打印；當(dāng)前節(jié)點(diǎn)的話存在左右節(jié)點(diǎn)的話，先放入左節(jié)點(diǎn)，再放入右節(jié)點(diǎn)。如果不存在孩子節(jié)點(diǎn)，等隊(duì)列為null的話，就停止輸出。但是，存在一個(gè)問題，我們不知道哪些節(jié)點(diǎn)是類屬于一層的，因此需要進(jìn)行指定。需要引入哈希表來(lái)統(tǒng)計(jì)相關(guān)的層數(shù)、以及最大的跨度

使用哈希表

• 引入哈希表，設(shè)置三個(gè)變量，max為全局最大寬度，w為統(tǒng)計(jì)當(dāng)前層級(jí)的寬度值，level記錄統(tǒng)計(jì)層級(jí)
• 初始設(shè)置max=-1，w=0，level=1；當(dāng)a輸入隊(duì)列，w變?yōu)?，level顯示當(dāng)前層級(jí)為1，當(dāng)a出隊(duì)列，將其孩子節(jié)點(diǎn)b和c放入隊(duì)列，當(dāng)b出隊(duì)列，level查詢發(fā)現(xiàn)b是2層的，因此將w和max比較大小，將大的數(shù)值賦值給max，然后將w清除數(shù)據(jù)，重新統(tǒng)計(jì)第二層級(jí)的數(shù)的個(gè)數(shù)。以此類推。

代碼

package class05;import java.util.HashMap; import java.util.LinkedList; import java.util.Queue;public class Code03_TreeMaxWidth {public static class Node {public int value;public Node left;public Node right;public Node(int data) {this.value = data;}}public static int w(Node head) {if(head == null) {return 0;}Queue<Node> queue = new LinkedList<>();queue.add(head);HashMap<Node, Integer> levelMap = new HashMap<>();levelMap.put(head, 1);int curLevel = 1;int curLevelNodes = 0;int max = Integer.MIN_VALUE;while(!queue.isEmpty()) {Node cur = queue.poll();int curNodeLevel = levelMap.get(cur);if(curNodeLevel == curLevel) {curLevelNodes++;} else {max = Math.max(max, curLevelNodes);curLevel++;curLevelNodes = 1;}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);}}return max;}public static int getMaxWidth(Node head) {if (head == null) {return 0;}int maxWidth = 0;int curWidth = 0;// 目前的層數(shù)int curLevel = 0;// node 所在的層數(shù)HashMap<Node, Integer> levelMap = new HashMap<>();levelMap.put(head, 1);LinkedList<Node> queue = new LinkedList<>();queue.add(head);Node node = null;Node left = null;Node right = null;while (!queue.isEmpty()) {node = queue.poll();left = node.left;right = node.right;if (left != null) {levelMap.put(left, levelMap.get(node) + 1);queue.add(left);}if (right != null) {levelMap.put(right, levelMap.get(node) + 1);queue.add(right);}if (levelMap.get(node) > curLevel) {curWidth = 1;curLevel = levelMap.get(node);} else {curWidth++;}maxWidth = Math.max(maxWidth, curWidth);//更新最后一層，因?yàn)樽詈笠粚記]有觸發(fā)邏輯}return maxWidth;}public static void main(String[] args) {// TODO Auto-generated method stub}}

?二叉樹的遞歸套路

如何判斷一棵樹是滿二叉樹

• 性質(zhì) 節(jié)點(diǎn)數(shù) = 2^樹的高度 - 1
• 思路 假設(shè)以x為頭節(jié)點(diǎn)，只有滿足性質(zhì)才是一個(gè)滿二叉樹。在容許向左右兩個(gè)孩子要信息的前提下，應(yīng)該要什么信息，才可以解決問題。

public class IsFull{public static class Node{public int value;public Node left;public Node right;public Node(int data){this.value = data;}}public static boolean isFull(Node head){Info info = processInfo(head);int size = info.size;int height = info.height;return size == (1<<height) - 1;}public static class Info{public int size;public int height;public Info(int s,int h){size = s;height = h;}}public static Info processInfo(Node x){if(x == 0){return new Info(0,0);}Info leftInfo = processInfo(x.left);Info rightInfo = processInfo(x.right);int size = leftInfo.size + rightInfo.size + 1;int height = Math.max(leftInfo.height,rightInfo.height) + 1;return new Info(size, height);}public static void main(String[] args) {} }

方法歸納

• 假設(shè)要求以x為頭的答案
• 向左右兩個(gè)孩子要信息，去分析構(gòu)成答案的主要元素
• 確定向左右孩子要的信息，有可能左右要的信息不一樣
• 組織收集到的信息

判斷以x為頭的二叉樹是否是平衡二叉樹

• 判斷左右孩子的高度差是否相差小于等于1
• 如果左右孩子不滿足平衡二叉樹，那么此平衡二叉樹不成立

代碼

import jdk.vm.ci.code.site.Infopoint;public class IsFull{public static class Node{public int value;public Node left;public Node right;public Node(int data){this.value = data;}}public static class Info{public boolean isBalanced;public int height;public Info(boolean is,int h){isBalanced = is;height = h;}}public static Info process(Node x){if(x == nll){return new Info(true,0);//return null;}Info leftInfo = process(x.left);Info rightInfo = process(x.right);int subTreeMaxHeight = 0;if(leftInfo != null){subTreeMaxHeight = leftInfo.height;}if(rightInfo!=null){subTreeMaxHeight = Math.max(subTreeMaxHeight,rightInfo.height);}int height = 1 + subTreeMaxHeight;boolean isBalanced = true;if(leftInfo!=null && !leftInfo.isBalanced){isBalanced=false;}if(rightInfo!= null && !rightInfo.isBalanced){isBalanced = false;}int leftH = leftInfo != null ? leftInfo.height : 0;int rightH = leftInfo != null ? rightInfo.height : 0; if(Math.abs(leftH - rightH)>1){isBalanced = false;}return new Infopoint(isBalanced, height);}public static void main(String[] args) {} }

求樹中兩個(gè)節(jié)點(diǎn)的最大距離

情況分類

和頭節(jié)點(diǎn)x無(wú)關(guān)

• 左樹上的最大距離
• 右樹上的最大距離

和頭節(jié)點(diǎn)x相關(guān)

• 左邊距離x最遠(yuǎn)和x到右邊最遠(yuǎn)距離（樹的高度）

代碼

import org.graalvm.compiler.nodes.calc.LeftShiftNode; import org.graalvm.compiler.nodes.calc.RightShiftNode;import jdk.vm.ci.code.site.Infopoint;public class IsFull{public static int maxDistance(Node head){Info info = process(head);return info.maxDistance;}public static class Info{public int maxDistance;public int height;public Info(boolean is,int h){maxDistance = d;height = h;}}public static Info process(Node x){if(x == null){return new Info(0,0);}Info leftInfo = process(x.left);Info rightInfo = process(x.right);int height = Math.max(leftInfo.height,rightInfo.height) + 1;int maxDistance = Math.max(leftInfo.height + rightInfo.height + 1,Math.max(leftInfo.height,rightInfo.height));return new Info(maxDistance,height);} public static void main(String[] args) {} }

判斷一個(gè)樹是否是搜索二叉樹

套路

判定條件

• 左樹是否是搜索二叉樹
• 右樹是否是搜索二叉樹
• 左邊最大的是否小于 x節(jié)點(diǎn)
• 右邊最小的是否大于 x節(jié)點(diǎn)

代碼

package class05;import java.util.LinkedList; import java.util.Stack;import class05.Code01_PreInPosTraversal.Node;public class Code04_IsBST {public static class Node {public int value;public Node left;public Node right;public Node(int data) {this.value = data;}}public static class ReturnData {public boolean isBST;public int min;public int max;public ReturnData(boolean is, int mi, int ma) {isBST = is;min = mi;max = ma;}}public static ReturnData process(Node x) {if(x == null) {return null;}ReturnData leftData = process(x.left);ReturnData rightData = process(x.right);int min = x.value;int max = x.value;if(leftData!=null) {min = Math.min(min, leftData.min);max = Math.max(max, leftData.max);}if(rightData!=null) {min = Math.min(min, rightData.min);max = Math.max(max, rightData.max);} // boolean isBST = true; // if(leftData!=null && (!leftData.isBST || leftData.max >= x.value )) { // isBST= false; // } // if(rightData!=null && ( !rightData.isBST || x.value >= rightData.min )) { // isBST= false; // }boolean isBST = false;if((leftData != null ? (leftData.isBST && leftData.max < x.value) : true)&&(rightData !=null ? (rightData.isBST && rightData.min > x.value) : true) ) {isBST = true;}return new ReturnData(isBST, min, max);}public static boolean isF(Node head) {if(head == null) {return true;}Info data = f(head);return data.nodes == (1 << data.height - 1);}public static class Info{public int height;public int nodes;public Info(int h, int n) {height = h;nodes = n;}}public static Info f(Node x) {if(x == null) {return new Info(0,0);}Info leftData = f(x.left);Info rightData = f(x.right);int height = Math.max(leftData.height,rightData.height)+1;int nodes = leftData.nodes + rightData.nodes + 1;return new Info(height, nodes);}public static boolean inOrderUnRecur(Node head) {if (head == null) {return true;}int pre = Integer.MIN_VALUE;Stack<Node> stack = new Stack<Node>();while (!stack.isEmpty() || head != null) {if (head != null) {stack.push(head);head = head.left;} else {head = stack.pop();if (head.value <= pre) {return false;}pre = head.value;head = head.right;}}return true;}public static boolean isBST(Node head) {if (head == null) {return true;}LinkedList<Node> inOrderList = new LinkedList<>();process(head, inOrderList);int pre = Integer.MIN_VALUE;for (Node cur : inOrderList) {if (pre >= cur.value) {return false;}pre = cur.value;}return true;}public static void process(Node node, LinkedList<Node> inOrderList) {if (node == null) {return;}process(node.left, inOrderList);inOrderList.add(node);process(node.right, inOrderList);}}

也可以中序遍歷

• 只要遞增，就是搜索二叉樹

• 基于非遞歸中序遍歷改進(jìn)，由先前的打印，變?yōu)楹颓耙粋€(gè)節(jié)點(diǎn)比較

代碼

public static boolean inOrderUnRecur(Node head){if(head == null){return true;}int pre = Integer.MIN_VALUE;Stack<Node> stack = new Stack<Node>();while(!stack.isEmpty() || head != null){if(head != null){stack.push(head);head = head.left;}else{head = stack.pop();if(head.value <= pre){return false;}pre = head.value;head = head.right;}}return true;}

不可以使用套路來(lái)做

判斷一棵樹是否是完全二叉樹

• 如果使用條件，左子樹是否是完全二叉樹，右子樹是否是完全二叉樹來(lái)判定根節(jié)點(diǎn)是否是完全二叉樹

• 即使左子樹和右子樹都是完全二叉樹，但是左子樹比右子樹少整整一層的情形下，判定失敗

思路

• 寬度優(yōu)先遍歷，任何一個(gè)節(jié)點(diǎn)不能有右節(jié)點(diǎn)，沒有左節(jié)點(diǎn)。
• 當(dāng)?shù)谝淮伟l(fā)現(xiàn)某節(jié)點(diǎn)左右不雙全，后續(xù)節(jié)點(diǎn)都是右節(jié)點(diǎn)

package class05;import java.util.LinkedList;public class Code05_IsCBT {public static class Node {public int value;public Node left;public Node right;public Node(int data) {this.value = data;}}public static boolean isCBT(Node head) {if (head == null) {return true;}LinkedList<Node> queue = new LinkedList<>();// 是否遇到過左右兩個(gè)孩子不雙全的節(jié)點(diǎn)boolean leaf = false;Node l = null;Node r = null;queue.add(head);while (!queue.isEmpty()) {head = queue.poll();l = head.left;r = head.right;if (// 如果遇到了不雙全的節(jié)點(diǎn)之后，又發(fā)現(xiàn)當(dāng)前節(jié)點(diǎn)不是葉節(jié)點(diǎn)(leaf && !(l == null && r == null)) || (l == null && r != null)) {return false;}if (l != null) {queue.add(l);}if (r != null) {queue.add(r);}if (l == null || r == null) {leaf = true;}}return true;}}

求n1和n2的最低公共主先

劃分情況（x為頭節(jié)點(diǎn)）

• x無(wú)n1和n2
• x只有n1
• x只有n2
• x有n1和n2：左n1n2；右n1n2；左n1右n2；左n2右n1

代碼

package class05;import java.util.HashMap; import java.util.HashSet;public class Code07_LowestCommonAncestor {public static class Node {public int value;public Node left;public Node right;public Node(int data) {this.value = data;}}public static Node lowestAncestor(Node head, Node o1, Node o2) {if (head == null || head == o1 || head == o2) { // base casereturn head;}Node left = lowestAncestor(head.left, o1, o2);Node right = lowestAncestor(head.right, o1, o2);if (left != null && right != null) {return head;}// 左右兩棵樹，并不都有返回值return left != null ? left : right;}public static class Record1 {private HashMap<Node, Node> map;public Record1(Node head) {map = new HashMap<Node, Node>();if (head != null) {map.put(head, null);}setMap(head);}private void setMap(Node head) {if (head == null) {return;}if (head.left != null) {map.put(head.left, head);}if (head.right != null) {map.put(head.right, head);}setMap(head.left);setMap(head.right);}public Node query(Node o1, Node o2) {HashSet<Node> path = new HashSet<Node>();while (map.containsKey(o1)) {path.add(o1);o1 = map.get(o1);}while (!path.contains(o2)) {o2 = map.get(o2);}return o2;}}public static class Record2 {private HashMap<Node, HashMap<Node, Node>> map;public Record2(Node head) {map = new HashMap<Node, HashMap<Node, Node>>();initMap(head);setMap(head);}private void initMap(Node head) {if (head == null) {return;}map.put(head, new HashMap<Node, Node>());initMap(head.left);initMap(head.right);}private void setMap(Node head) {if (head == null) {return;}headRecord(head.left, head);headRecord(head.right, head);subRecord(head);setMap(head.left);setMap(head.right);}private void headRecord(Node n, Node h) {if (n == null) {return;}map.get(n).put(h, h);headRecord(n.left, h);headRecord(n.right, h);}private void subRecord(Node head) {if (head == null) {return;}preLeft(head.left, head.right, head);subRecord(head.left);subRecord(head.right);}private void preLeft(Node l, Node r, Node h) {if (l == null) {return;}preRight(l, r, h);preLeft(l.left, r, h);preLeft(l.right, r, h);}private void preRight(Node l, Node r, Node h) {if (r == null) {return;}map.get(l).put(r, h);preRight(l, r.left, h);preRight(l, r.right, h);}public Node query(Node o1, Node o2) {if (o1 == o2) {return o1;}if (map.containsKey(o1)) {return map.get(o1).get(o2);}if (map.containsKey(o2)) {return map.get(o2).get(o1);}return null;}}// for test -- print treepublic 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) {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);head.right.right.left = new Node(8);printTree(head);System.out.println("===============");Node o1 = head.left.right;Node o2 = head.right.left;System.out.println("o1 : " + o1.value);System.out.println("o2 : " + o2.value);System.out.println("ancestor : " + lowestAncestor(head, o1, o2).value);System.out.println("===============");}}

?

總結(jié)

以上是生活随笔為你收集整理的算法入门篇六 二叉树的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。