Niu Guest network algorithm entry left cheng Yun teacher personal review, if the invasion, set to private

Binary tree traversal (recursion)

  • Sequential traversal (middle, left, right)

  • Middle order traversal (left, middle, right)

  • Post-order traversal (left, right, middle)

​

  • As the structure shown in the figure above, the traversal of binary tree is recursive in nature. Each node 1, 2 and 3 will appear three times. For example, starting from node 1 and coming to node 2, the left side of node 2 is empty, return and print 2; the right side is empty, return and print 2; then return to node 1, similar to node 3. So the final output sequence is 1,2,2,2,1,3,3,3,1.
  • If you print the first element in the recursion, you are traversing first
  • If you print the element that recurses the second time, it is middle-order traversal
  • If you print the element that appears the third time in the recursion, it is a post-order traversal

Binary tree traversal (non-recursive)

The first sequence traversal

​

  • The binary tree structure is shown in the figure, with a stack prepared to receive data
  • There are only two principles: 1. The popup node on the stack is called cur (current node), and the popup is printed; 2. Print the right node of cur first, and print the left node. Stop when the stack is empty.
  • 1 pushes, pops 1, prints 1; Push 3 and 2 onto the stack, pop 2, print 2, and push 2’s children 4 and 5 onto the stack; Because you put the right first, then the left, so you put the five first, then the four; Pop 4, print 4; As mentioned above, the sequential traversal is 1,2,4,5,3,6,7

code

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) { // 1 if (head == null) { return; } // 1 f(head.left); //2 //2 f(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); // recursive System.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(); // unrecursive System.out.println("============unrecursive============="); preOrderUnRecur(head); inOrderUnRecur(head); posOrderUnRecur1(head); posOrderUnRecur2(head); }}Copy the code

Middle-order traversal (non-recursive)

  • There are only two principles: 1. The popup node on the stack is called cur (current node), and the popup is printed; 2. Print the left node of cur first, and print the right node. If there is no left node, no operation is required. Stop when the stack is empty.
  • Constantly divide the right node into left and middle nodes

Post-order traversal (non-recursive)

  • There are only two principles: 1, the popup node in the stack is called cur (current node), popup does not print, put in a new stack; 2. Finally, print the elements in the second stack, equivalent to (left, right, middle), i.e. post-order traversal

Intuitive printing of binary trees

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); }}Copy the code

Find the maximum width of a binary tree

​

Using the queue

  • Use a queue, entering from the head and exiting from the tail;
  • Principle: pop up the current node cur, pop up and print; If the current node has left and right nodes, put the left node first and then the right node. If there is no child node, wait until the queue is null, then stop output. One problem, however, is that we do not know which nodes belong to the first layer, so we need to specify them. Hash tables need to be introduced to count the number of related layers, as well as the maximum span

​

Use hash tables

  • Introduce hash table, set three variables, Max is the global maximum width, w is the width value of the current level of statistics, level records the level of statistics
  • Max =-1, w=0, level=1; Become 1, when a input queue, w level shows the current level of 1, when a queue, the child node b and c in the queue, queue, when b level query found that b is 2 layers, so compare w with Max size, will be a big value assigned to the Max, then w clear data, count of the number of the second layer. And so on.

code

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; Int curLevel = 0; // levelMap < 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); // Update the last layer because the last layer does not trigger logic} return maxWidth; } public static void main(String[] args) { // TODO Auto-generated method stub } }Copy the code

Recursive routines of binary trees

How do you tell if a tree is full binary

  • Number of properties = 2^ height of the tree – 1

  • If we assume that x is the first node, we’re going to have a full binary tree only if we satisfy this property. On the premise of allowing the two children to ask for information, what information should be needed to solve the problem.

    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) { }Copy the code

    }

Methods of induction

  • Let’s say I want an answer that starts with x
  • Ask the left and right children for information to analyze the main elements that make up the answer
  • Be sure to ask your left and right children for information that may be different
  • Information collected by the organization

Determine whether a binary tree starting with x is a balanced binary tree

  • Determine whether the height difference between the left and right children is less than or equal to 1
  • If the left and right children do not satisfy the balanced binary tree, then the balanced binary tree is not valid

code

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) { } }Copy the code

Find the maximum distance between two nodes in a tree

Case classification

It’s independent of the head node x

  • Maximum distance on the left tree
  • Maximum distance on the right tree

It’s associated with the head node X

  • Farthest left from x and farthest right from X (height of tree)

code

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) { } }Copy the code

Determine if a tree is a search binary tree

routine

Decision condition

  • The left tree is a search binary tree
  • The right tree is a search binary tree
  • Is the largest on the left less than the x node
  • Is the smallest on the right greater than the x node

code

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); }}Copy the code

You can also iterate in middle order

  • As long as it increments, it’s a search binary tree

  • An improvement based on sequential traversal in non-recursion, instead of printing previously, to compare with the previous node

code

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; }Copy the code

You can’t do it using routines

Determine if a tree is a perfect binary tree

  • If you use the condition, is the left subtree a complete binary tree, is the right subtree a complete binary tree to determine whether the root node is a complete binary tree

  • Even if both the left and right subtrees are complete binary trees, the left subtree has a whole layer less than the right subtree, the decision fails

Train of thought

  • Width first traversal, no node can have a right node, no left node.

  • When the left and right sides of a node are discovered for the first time, all subsequent nodes are right nodes

    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<>(); 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 (// if the current node is not a leaf node (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; }Copy the code

    }

Find the lowest common primacy of n1 and n2

Partition (x is the head node)

  • X None N1 and n2
  • X only n1
  • X only n2
  • X has n1 and n2: left N1n2; Right n1n2; N1, left, N2, right; Left right n1 n2

code

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 case return 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 tree 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(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("==============="); }}Copy the code

​