Some topics related to data structures and algorithms in binary trees

Recently summarized some data structure and algorithm related topics, this is the first article about binary trees. First the data structure of the binary tree:

Class TreeNode{ int val; //left child TreeNode left; //right child TreeNode right;}

The problem of binary trees can generally be solved by recursive and iterative methods.

1. Find the maximum depth of the binary tree

Int maxDeath(TreeNode node){ if(node==null){ return 0; } int left = maxDeath(node.left); int right = maxDeath(node.right); return Math.max(left,right) + 1 ;}

2. Find the minimum depth of the binary tree

Int getMinDepth(TreeNode root){ if(root == null){ return 0; } return getMin(root); } int getMin(TreeNode root){ if(root == null){ return Integer.MAX_VALUE; } if(root .left == null&&root.right == null){ return 1; } return Math.min(getMin(root.left),getMin(root.right)) + 1; }

3. Find the number of nodes in the binary tree

Int numOfTreeNode(TreeNode root){ if(root == null){ return 0; } int left = numOfTreeNode(root.left); int right = numOfTreeNode(root.right); return left + right + 1; }

4. Find the number of leaf nodes in the binary tree

Int numsOfNoChildNode(TreeNode root){ if(root == null){ return 0; } if(root.left==null&&root.right==null){ return 1; } return numsOfNodeTreeNode(root.left)+numsOfNodeTreeNode(root. Right); }

5. Find the number of nodes in the k-th layer in the binary tree

Int numsOfkLevelTreeNode(TreeNode root,int k){ if(root == null||k<1){ return 0; } if(k==1){ return 1; } int numsLeft = numsOfkLevelTreeNode(root.left,k- 1); int numsRight = numsOfkLevelTreeNode(root.right,k-1); return numsLeft + numsRight; }

6. Determine if the binary tree is a balanced binary tree

Boolean isBalanced(TreeNode node){ return maxDeath2(node)!=-1; } int maxDeath2(TreeNode node){ if(node ​​== null){ return 0; } int left = maxDeath2(node.left); int right = maxDeath2(node.right); if(left==-1||right==-1||Math.abs(left-right)>1){ return -1; } return Math.max(left, right) + 1; }

7. Determine if the binary tree is a complete binary tree

What is a complete binary tree? See

Boolean isCompleteTreeNode(TreeNode root){ if(root == null){ return false; } Queue Queue = new LinkedList (); queue.add(root); boolean result = true; boolean hasNoChild = false; while(!queue.isEmpty()){ TreeNode current = queue.remove(); if(hasNoChild){ if(current.left! =null||current.right!=null){ result = false; break; } }else{ if(current.left!=null&¤t.right!=null){ queue.add(current.left); queue. Add(current.right); }else if(current.left!=null&¤t.right==null){ queue.add(current.left); hasNoChild = true; }else if(current.left==null&¤ T.right!=null){ result = false; break; }else{ hasNoChild = true; } } } return result; }

8. Are the two binary trees identical?

Boolean isSameTreeNode(TreeNode t1,TreeNode t2){ if(t1==null&&t2==null){ return true; } else if(t1==null||t2==null){ return false; } if(t1.val ! = t2.val){ return false; } boolean left = isSameTreeNode(t1.left,t2.left); boolean right = isSameTreeNode(t1.right,t2.right); return left&&right; }

9. Are the two binary trees mirroring each other?

Boolean isMirror(TreeNode t1,TreeNode t2){ if(t1==null&&t2==null){ return true; } if(t1==null||t2==null){ return false; } if(t1.val != T2.val){ return false; } return isMirror(t1.left,t2.right)&&isMirror(t1.right,t2.left); }

10. Flip the binary tree or mirror the binary tree

TreeNode mirrorTreeNode(TreeNode root){ if(root == null){ return null; } TreeNode left = mirrorTreeNode(root.left); TreeNode right = mirrorTreeNode(root.right); root.left = right; root.right = left ; return root; }

11. Find the lowest common ancestor node of the two binary trees

TreeNode getLastCommonParent(TreeNode root,TreeNode t1,TreeNode t2){ if(findNode(root.left,t1)){ if(findNode(root.right,t2)){ return root; }else{ return getLastCommonParent(root.left, T1,t2); } }else{ if(findNode(root.left,t2)){ return root; }else{ return getLastCommonParent(root.right,t1,t2) } } } // Find if the node node is in the current binary tree Boolean findNode(TreeNode root,TreeNode node){ if(root == null || node == null){ return false; } if(root == node){ return true; } boolean found = findNode(root.left, Node); if(!found){ found = findNode(root.right,node); } return found; }

12. Preorder traversal of the binary tree

Iterative solution

ArrayList preOrder(TreeNode root){ Stack Stack = new Stack (); ArrayList List = new ArrayList (); if(root == null){ return list; } stack.push(root); while(!stack.empty()){ TreeNode node = stack.pop(); list.add(node.val); If(node.right!=null){ stack.push(node.right); } if(node.left != null){ stack.push(node.left); } } return list; }

Recursive solution

ArrayList preOrderReverse(TreeNode root){ ArrayList Result = new ArrayList (); preOrder2(root, result); return result; } void preOrder2(TreeNode root, ArrayList Result){ if(root == null){ return; } result.add(root.val); preOrder2(root.left,result); preOrder2(root.right,result); }

13. The in-order traversal of the binary tree

ArrayList inOrder(TreeNode root){ ArrayList List = new ArrayList< (); Stack Stack = new Stack (); TreeNode current = root; while(current != null|| !stack.empty()){ while(current != null){ stack.add(current); current = current.left; } current = stack. Peek(); stack.pop(); list.add(current.val); current = current.right; } return list; }

14. Post-order traversal of the binary tree

ArrayList postOrder(TreeNode root){ ArrayList List = new ArrayList (); if(root == null){ return list; } list.addAll(postOrder(root.left)); list.addAll(postOrder(root.right)); list.add(root.val); return list ; }

15. Preorder traversal and post-order traversal construct binary tree

TreeNode buildTreeNode(int[] preorder,int[] inorder){ if(preorder.length!=inorder.length){ return null; } return myBuildTree(inorder,0,inorder.length-1,preorder,0,preorder.length -1); } TreeNode myBuildTree(int[] inorder, int start, int inend, int[] preorder, int prestart, int preend){ if(instart>inend){ return null; } TreeNode root = new TreeNode(preorder[ Prestart]); int position = findPosition(inorder,instart,inend,preorder[start]); root.left = myBuildTree(inorder,instart,position-1,preorder,prestart+1,prestart+position-instart); root. Right = myBuildTree(inorder,position+1,inend,preorder,position-inend+preend+1,preend); return root; } int findPosition(int[] arr,int start,int end,int key){ int i; For(i = start;i<=end;i++){ if(arr[i] == key){ return i; } } return -1; }

16. Insert a node in the binary tree

TreeNode insertNode(TreeNode root,TreeNode node){ if(root == node){ return node; } TreeNode tmp = new TreeNode(); tmp = root; TreeNode last = null; while(tmp!=null){ last = tmp ; if(tmp.val>node.val){ tmp = tmp.left; }else{ tmp = tmp.right; } } if(last!=null){ if(last.val>node.val){ last. Left = node; }else{ last.right = node; } } return root; }

17. Enter a binary tree and an integer to print out the sum of the node values ​​in the binary tree equal to the path of the input integer.

Void findPath(TreeNode r,int i){ if(root == null){ return; } Stack Stack = new Stack (); int currentSum = 0; findPath(r, i, stack, currentSum); } void findPath(TreeNode r, int i,Stack Stack, int currentSum){ currentSum+=r.val; stack.push(r.val); if(r.left==null&&r.right==null){ if(currentSum==i){ for(int path:stack ) { System.out.println(path); } } } if(r.left!=null){ findPath(r.left, i, stack, currentSum); } if(r.right!=null){ findPath( R.right, i, stack, currentSum); } stack.pop(); }

18. Binary tree search interval

Given two values ​​k1 and k2(k1 < k2) and the root node of a binary search tree. Find all nodes in the tree whose values ​​are in the range k1 to k2. That is, print all x (k1 <= x <= k2) where x is the node value in the binary search tree. Returns all ascending node values.

ArrayList Result; ArrayList searchRange(TreeNode root,int k1,int k2){ result = new ArrayList (); searchHelper(root,k1,k2); return result; } void searchHelper(TreeNode root,int k1,int k2){ if(root == null){ return; } if(root.val>k1){ searchHelper (root.left,k1,k2); } if(root.val>=k1&&root.val<=k2){ result.add(root.val); } if(root.val

19. Hierarchical traversal of binary trees

ArrayList > levelOrder(TreeNode root){ ArrayList > result = new ArrayList >(); if(root == null){ return result; } Queue Queue = new LinkedList (); queue.offer(root); while(!queue.isEmpty()){ int size = queue.size(); ArrayList< Level = new ArrayList (): for(int i = 0;i < size ;i++){ TreeNode node = queue.poll(); level.add(node.val); if(node.left != null){ queue.offer(node .left); } if(node.right != null){ queue.offer(node.right); } } result.add(Level); } return result; }

20. The longest distance between two nodes in a binary tree

The longest distance between two nodes in a binary tree may have three cases: 1. The maximum depth of the left subtree + the maximum depth of the right subtree is the longest distance of the binary tree 2. The longest distance in the left subtree is the most of the binary tree Long distance 3. The longest distance of the right subtree is the longest distance of the binary tree. Therefore, recursive solution can be

Private static class Result{ int maxDistance; int maxDepth; public Result() { } public Result(int maxDistance, int maxDepth) { this.maxDistance = maxDistance; this.maxDepth = maxDepth; } } int getMaxDistance(TreeNode root){ return getMaxDistanceResult (root).maxDistance; } Result getMaxDistanceResult(TreeNode root){ if(root == null){ Result empty = new Result(0,-1); return empty; } Result lmd = getMaxDistanceResult(root.left); Result rmd = getMaxDistanceResult(root.right); Result result = new Result(); result.maxDepth = Math.max(lmd.maxDepth,rmd.maxDepth) + 1; result.maxDistance = Math.max(lmd.maxDepth + rmd.maxDepth , Math.max(lmd.maxDistance,rmd.maxDistance)); return result; }

21. Different binary trees

Given n, ask how many different binary search trees are composed of 1...n nodes?

Int numTrees(int n ){ int[] counts = new int[n+2]; counts[0] = 1; counts[1] = 1; for(int i = 2;i<=n;i++){ for (int j = 0;j

22. Determine if the binary tree is a legal binary search tree (BST)

A BST is defined as: the value in the left subtree of the node is strictly less than the value of the node. The value in the right subtree of the node is strictly greater than the value of the node. The left and right subtrees must also be binary search trees. The tree of a node is also a binary search tree.

Public int lastVal = Integer.MAX_VALUE; public boolean firstNode = true; public boolean isValidBST(TreeNode root) { // write your code here if(root==null){ return true; } if(!isValidBST(root.left)) { return false; } if(!firstNode&&lastVal >= root.val){ return false; } firstNode = false; lastVal = root.val; if (!isValidBST(root.right)) { return false; } return true; }

Deep understanding of the solution ideas of these questions, there should be no problem in the binary tree problem in the interview.

Ningbo Autrends International Trade Co.,Ltd. , https://www.supermosvape.com