栈队列链表二叉树
栈和队列
1. 栈的实现
1 import java.util.EmptyStackException; 2 3 //基于数组实现的栈 4 public class ArrayStack { 5 private int[] arr; 6 private int top; 7 8 ArrayStack(int initialSize){ 9 if(initialSize<=0) 10 throw new RuntimeException("非法初始化参数："+initialSize); 11 top=-1; 12 arr=new int[initialSize]; 13 } 14 15 public int push(int x){ 16 if(top==arr.length-1) 17 throw new StackOverflowError(); 18 arr[++top]=x; 19 return x; 20 } 21 22 public int pop(){ 23 if(top<0) 24 throw new EmptyStackException(); 25 return arr[top--]; 26 } 27 28 public int peek(){ 29 if(top<0) 30 throw new EmptyStackException(); 31 return arr[top]; 32 } 33 34 public boolean isEmpty(){ 35 return top==-1; 36 } 37 38 }
1 import java.util.EmptyStackException; 2 import java.util.LinkedList; 3 4 //基于链表实现栈 5 public class ListStack { 6 private LinkedList<Integer> list=new LinkedList<>(); 7 8 public int push(int x){ 9 list.addLast(x); 10 return x; 11 } 12 13 public int pop(){ 14 if(list.size()<=0) 15 throw new EmptyStackException(); 16 return list.removeLast(); 17 } 18 19 public int peek(){ 20 if(list.size()<=0) 21 throw new EmptyStackException(); 22 return list.getLast(); 23 } 24 25 public boolean isEmpty(){ 26 return list.size()==0; 27 } 28 29 }
2. 队列实现
1 /** 2 * 顺序队列的假溢出 3 * 改进为循环队列 4 * head指向队列的第一个元素 5 * tail指向队尾的下一个位置 6 * 实际存储的元素数为len-1(区分队列空和队列满的情况) 7 */ 8 public class ArrayQueue { 9 private int[] arr; 10 private int head; 11 private int tail; 12 private int len; 13 14 ArrayQueue(int len){ 15 this.len = len; 16 arr = new int[len]; 17 } 18 19 public int offer(int x){ 20 if((tail+1)%len==head){ 21 throw new RuntimeException("circle queue is Full"); 22 }else { 23 arr[tail]=x; 24 tail=(tail+1)%len; 25 return x; 26 } 27 } 28 29 public int poll(){ 30 if(head==tail){ 31 throw new RuntimeException("circle queue is Null"); 32 }else{ 33 int n=arr[head]; 34 head=(head+1)%len; 35 return n; 36 } 37 } 38 39 }
1 import java.util.LinkedList; 2 import java.util.Queue; 3 4 public class ListQueue { 5 private Queue<Integer> queue=new LinkedList<>(); 6 7 public int peek(){ 8 return queue.peek(); 9 } 10 11 public boolean offer(int x){ 12 return queue.offer(x); 13 } 14 15 public int poll(){ 16 return queue.poll(); 17 } 18 19 public boolean isEmpty() { 20 return queue.isEmpty(); 21 } 22 23 }
3. 两个栈实现一个队列
1 import java.util.Stack; 2 3 public class MyQueue { 4 private Stack<Integer> stack=new Stack<>(); 5 private Stack<Integer> out=new Stack<>(); 6 7 public int offer(int x){ 8 stack.push(x); 9 return x; 10 } 11 12 public int poll(){ 13 if(out.isEmpty()) 14 while(!stack.isEmpty()) 15 out.push(stack.pop()); 16 17 if(out.isEmpty()) 18 throw new RuntimeException("队列为空！"); 19 return out.pop(); 20 } 21 22 }
4. 两个队列实现一个栈
1 import java.util.EmptyStackException; 2 import java.util.LinkedList; 3 import java.util.Queue; 4 5 public class MyStack { 6 private Queue<Integer> queue=new LinkedList<>(); 7 private Queue<Integer> queue2=new LinkedList<>(); 8 9 public int push(int x){ 10 if(!queue.isEmpty()) 11 queue.offer(x); 12 else 13 queue2.offer(x); 14 return x; 15 } 16 17 public int pop(){ 18 if(queue.isEmpty()&&queue2.isEmpty()) 19 throw new EmptyStackException(); 20 if(queue.isEmpty()){ 21 while(queue2.size()>1) 22 queue.offer(queue2.poll()); 23 return queue2.poll(); 24 }else{ 25 while(queue.size()>1) 26 queue2.offer(queue.poll()); 27 return queue.poll(); 28 } 29 } 30 31 }
5. 设计含最小函数min的栈
1 import java.util.Stack; 2 3 public class MinStack { 4 Stack<Integer> stack; 5 Stack<Integer> stackMin; 6 7 public MinStack() { 8 this.stack=new Stack<>(); 9 this.stackMin=new Stack<>(); 10 } 11 12 public void push(int x) { 13 stack.push(x); 14 if(stackMin.isEmpty()) 15 stackMin.push(x); 16 else if(stackMin.peek()<x) 17 stackMin.push(stackMin.peek()); 18 else 19 stackMin.push(x); 20 } 21 22 public void pop() { 23 if(!stack.isEmpty()&&!stackMin.isEmpty()){ 24 stack.pop(); 25 stackMin.pop(); 26 }else{ 27 System.out.println("栈已经没有元素了..."); 28 } 29 } 30 31 public int top() { 32 return stack.peek(); 33 } 34 35 public int getMin() { 36 return stackMin.peek(); 37 } 38 }
6. 判断出栈序列是否合法
1 import java.util.Stack; 2 3 public class Main { 4 public static boolean IsPopOrder(int [] pushA,int [] popA) { 5 Stack<Integer> stack = new Stack<>(); 6 int popIndex = 0; 7 for(int i = 0; i< pushA.length;i++){ 8 stack.push(pushA[i]); 9 while(!stack.empty() &&stack.peek() == popA[popIndex]){ 10 stack.pop(); 11 popIndex++; 12 } 13 } 14 return stack.empty(); 15 } 16 17 }
链表
1 import java.util.HashSet; 2 import java.util.Stack; 3 4 public class List { 5 static class Node{ 6 int val; 7 Node next; 8 9 public Node(int val){ 10 this.val=val; 11 } 12 } 13 14 //创建链表 15 public Node head; 16 public Node current; 17 public void add(int val){ 18 if(head==null){ 19 head=new Node(val); 20 current=head; 21 }else { 22 current.next=new Node(val); 23 current=current.next; 24 } 25 } 26 27 //遍历输出链表 28 public static void print(Node head){ 29 if(head==null) 30 return; 31 Node cur=head; 32 while(cur.next!=null){ 33 System.out.print(cur.val+"->"); 34 cur=cur.next; 35 } 36 System.out.println(cur.val); 37 } 38 39 //获取链表节点数 40 public static int getLength(Node head){ 41 if(head==null) 42 return 0; 43 int count=0; 44 Node cur=head; 45 while(cur!=null){ 46 count++; 47 cur=cur.next; 48 } 49 return count; 50 } 51 52 //查找倒数第k个节点 53 public static int findLastNode(Node head,int k){ 54 if(k==0||head==null) 55 return -1; 56 int size=getLength(head); 57 if(k>size) 58 return -1; 59 Node cur=head; 60 for(int i=0;i<size-k;i++){ 61 cur=cur.next; 62 } 63 return cur.val; 64 } 65 //在不允许遍历链表长度的情况下查找倒数第k个节点 66 public static int findLastNode2(Node head,int k){ 67 if(k==0||head==null) 68 return -1; 69 Node fast=head,slow=head; 70 for(int i=0;i<k-1;i++){ 71 fast=fast.next; 72 if(fast==null) 73 return -1; 74 } 75 while(fast.next!=null){ 76 slow=slow.next; 77 fast=fast.next; 78 } 79 return slow.val; 80 } 81 82 //查找中间节点 83 public static int findMidNode(Node head){ 84 if(head==null) 85 return -1; 86 Node fast=head,slow=head; 87 while(fast!=null&&fast.next!=null){ 88 slow=slow.next; 89 fast=fast.next.next; 90 } 91 return slow.val; 92 } 93 94 //合并两个有序链表 95 public static Node mergeTwoLists(Node l1,Node l2){ 96 if(l1==null) 97 return l2; 98 if(l2==null) 99 return l1; 100 if(l1.val<l2.val){ 101 l1.next=mergeTwoLists(l1.next,l2); 102 return l1; 103 }else { 104 l2.next=mergeTwoLists(l1,l2.next); 105 return l2; 106 } 107 } 108 109 //循环翻转 110 public static Node reverseListByLoop(Node head){ 111 Node pre=null; 112 Node next=null; 113 while(head!=null){ 114 next=head.next; 115 head.next=pre; 116 pre=head; 117 head=next; 118 } 119 return pre; 120 } 121 //递归翻转 122 public static Node reverseListByRecursion(Node head){ 123 if(head==null||head.next==null) 124 return head; 125 Node pre=reverseListByRecursion(head.next); 126 head.next.next=head; 127 head.next=null; 128 return pre; 129 } 130 131 //反向打印链表 132 public static void reversePrint(Node head){ 133 if(head==null) 134 return; 135 Stack<Node> stack=new Stack<>(); 136 Node cur=head; 137 while(cur!=null){ 138 stack.push(cur); 139 cur=cur.next; 140 } 141 while(!stack.isEmpty()){ 142 System.out.print(stack.pop().val+" "); 143 } 144 System.out.println(); 145 } 146 147 //判断单链表是否有环 148 public static Node hasCycle(Node head){ 149 if(head==null) 150 return null; 151 Node fast=head,slow=head; 152 while(fast!=null&&fast.next!=null){ 153 slow=slow.next; 154 fast=fast.next.next; 155 if(slow==fast) 156 return slow; 157 } 158 return null; 159 } 160 161 //创建有环链表 162 public void add(Node node){ 163 if(node==null) 164 return; 165 if(head==null){ 166 head=node; 167 current=head; 168 }else { 169 current.next=node; 170 current=current.next; 171 } 172 } 173 //获取有环链表环的长度 174 public static int getCycleLength(Node node){ 175 Node cur=node; 176 int length=0; 177 while(cur!=null){ 178 cur=cur.next; 179 length++; 180 if(cur==node) 181 return length; 182 } 183 return length; 184 } 185 186 //获取环的起点 187 public static Node getCycleStart(Node head){ 188 if(head==null) 189 return null; 190 Node fast=head,slow=head; 191 while(fast!=null&&fast.next!=null){ 192 slow=slow.next; 193 fast=fast.next.next; 194 if(slow==fast){ 195 fast=head; 196 /* 197 假设链表起点到环的起点为x 198 链表起点到快慢指针相遇节点为x+z 199 环的长度为y 200 那么有2(x+z)-(x+z)=k*y 201 即x=k*y-z=y-z+(k-1)*y 202 */ 203 while(slow!=fast){ 204 slow=slow.next; 205 fast=fast.next; 206 } 207 return slow; 208 } 209 } 210 return null; 211 } 212 //获取环的起点2 213 public static Node getCycleStart2(Node head){ 214 HashSet<Node> set=new HashSet<>(); 215 while(head!=null){ 216 if(!set.add(head)) 217 return head; 218 head=head.next; 219 } 220 return null; 221 } 222 223 /* 224 获取两个单链表相交的第一个节点 225 1.压入栈中，依次比较找出最后一个相同的节点，时间空间复杂度均为O(len1+len2) 226 2.快慢指针 227 */ 228 public static Node getFirstCommonNode(Node l1,Node l2){ 229 if(l1==null||l2==null) 230 return null; 231 int len1=getLength(l1); 232 int len2=getLength(l2); 233 Node longHead=len1>len2?l1:l2,shortHead=len1>len2?l2:l1; 234 235 for(int i=0;i<Math.abs(len1-len2);i++) longHead=longHead.next; 236 while(longHead!=null&&shortHead!=null){ 237 if(longHead==shortHead) 238 return longHead; 239 longHead=longHead.next; 240 shortHead=shortHead.next; 241 } 242 return null; 243 } 244 245 }
二叉树
1 import java.util.*; 2 3 class TreeNode{ 4 int val; 5 TreeNode left; 6 TreeNode right; 7 8 public TreeNode(int val){ 9 this.val=val; 10 } 11 } 12 13 public class Tree { 14 //递归求二叉树节点个数 15 public static int getNodeNumByRecursion(TreeNode root){ 16 if(root==null) 17 return 0; 18 return getNodeNumByRecursion(root.left)+getNodeNumByRecursion(root.right)+1; 19 } 20 //迭代求二叉树节点个数 21 public static int getNodeNumByLoop(TreeNode root){ 22 if(root==null) 23 return 0; 24 int count=1; 25 Queue<TreeNode> queue=new LinkedList<>(); 26 queue.add(root); 27 28 while(!queue.isEmpty()){ 29 TreeNode cur=queue.remove(); 30 if(cur.left!=null){ 31 queue.add(cur.left); 32 count++; 33 } 34 if(cur.right!=null){ 35 queue.add(cur.right); 36 count++; 37 } 38 } 39 return count; 40 } 41 42 //递归求二叉树的深度 43 public static int getDepthByRecursion(TreeNode root){ 44 if(root==null) 45 return 0; 46 return Math.max(getDepthByRecursion(root.left),getDepthByRecursion(root.right))+1; 47 } 48 //迭代求二叉树的深度 49 public static int getDepthByLoop(TreeNode root){ 50 if(root==null) 51 return 0; 52 int depth=0; 53 int currentLevelNodes=1; 54 int nextLevelNodes=0; 55 Queue<TreeNode> queue=new LinkedList<>(); 56 queue.add(root); 57 58 while(!queue.isEmpty()){ 59 TreeNode cur=queue.remove(); 60 currentLevelNodes--; 61 if(cur.left!=null){ 62 queue.add(cur.left); 63 nextLevelNodes++; 64 } 65 if(cur.right!=null){ 66 queue.add(cur.right); 67 nextLevelNodes++; 68 } 69 if(currentLevelNodes==0){ 70 depth++; 71 currentLevelNodes=nextLevelNodes; 72 nextLevelNodes=0; 73 } 74 } 75 return depth; 76 } 77 78 //递归前序遍历 79 public static void preorderTraversalByRecursion(TreeNode root){ 80 if(root==null) 81 return; 82 System.out.print(root.val+" "); 83 preorderTraversalByRecursion(root.left); 84 preorderTraversalByRecursion(root.right); 85 } 86 //迭代前序遍历 87 public static void preorderTraversalByLoop(TreeNode root){ 88 if(root==null) 89 return; 90 Stack<TreeNode> stack=new Stack<>(); 91 stack.push(root); 92 93 while(!stack.isEmpty()){ 94 TreeNode cur=stack.pop(); 95 System.out.print(cur.val+" "); 96 if(cur.right!=null) 97 stack.push(cur.right); 98 if(cur.left!=null) 99 stack.push(cur.left); 100 } 101 } 102 103 //递归中序遍历 104 public static void inorderTraversalByRecursion(TreeNode root){ 105 if(root==null) 106 return; 107 inorderTraversalByRecursion(root.left); 108 System.out.print(root.val+" "); 109 inorderTraversalByRecursion(root.right); 110 } 111 //迭代中序遍历 112 //todo 113 public static void inorderTraversalByLoop(TreeNode root){ 114 if(root==null) 115 return; 116 Stack<TreeNode> stack=new Stack<>(); 117 TreeNode cur=root; 118 119 while(true){ 120 while(cur!=null){ 121 stack.push(cur); 122 cur=cur.left; 123 } 124 if(stack.isEmpty()) 125 break; 126 cur=stack.pop(); 127 System.out.print(cur.val+" "); 128 cur=cur.right; 129 } 130 } 131 132 //递归后序遍历 133 public static void postorderTraversalByRecursion(TreeNode root){ 134 if(root==null) 135 return; 136 postorderTraversalByRecursion(root.left); 137 postorderTraversalByRecursion(root.right); 138 System.out.print(root.val+" "); 139 } 140 //迭代后序遍历 141 //todo 142 public static void postorderTraversalByLoop(TreeNode root){ 143 if(root==null) 144 return; 145 Stack<TreeNode> stack=new Stack<>(); 146 Stack<TreeNode> output=new Stack<>(); 147 stack.push(root); 148 149 while(!stack.isEmpty()){ 150 TreeNode cur=stack.pop(); 151 output.push(cur); 152 if(cur.left!=null) 153 stack.push(cur.left); 154 if(cur.right!=null) 155 stack.push(cur.right); 156 } 157 while(!output.isEmpty()) System.out.print(output.pop().val+" "); 158 } 159 160 //递归分层遍历二叉树 161 //todo 162 public static void levelTraversalByRecursion(TreeNode root){ 163 ArrayList<ArrayList<Integer>> res=new ArrayList<>(); 164 dfs(root,0,res); 165 System.out.print(res); 166 167 } 168 private static void dfs(TreeNode root,int level,ArrayList<ArrayList<Integer>> res){ 169 if(root==null) 170 return; 171 if(level>=res.size()) 172 res.add(new ArrayList<>()); 173 res.get(level).add(root.val); 174 dfs(root.left,level+1,res); 175 dfs(root.right,level+1,res); 176 } 177 //迭代分层遍历二叉树 178 public static void levelTraversalByLoop(TreeNode root){ 179 if (root == null) 180 return; 181 LinkedList<TreeNode> queue = new LinkedList<>(); 182 queue.push(root); 183 184 while (!queue.isEmpty()) { 185 TreeNode cur = queue.removeFirst(); 186 System.out.print(cur.val + " "); 187 if (cur.left != null) queue.add(cur.left); 188 if (cur.right != null) queue.add(cur.right); 189 } 190 } 191 192 //递归 二叉查找树转为有序的双向链表 仅仅调节指针 193 //todo 需要仔细琢磨 194 public static TreeNode convertBST2DLLByRecursion(TreeNode root){ 195 root=convertBST2DLL(root); 196 while(root.left!=null) 197 root=root.left; 198 return root; 199 } 200 private static TreeNode convertBST2DLL(TreeNode root){ 201 if(root==null||(root.left==null&&root.right==null)) 202 return root; 203 TreeNode cur=null; 204 if(root.left!=null){ 205 cur=convertBST2DLL(root.left); 206 while(cur.right!=null) 207 cur=cur.right; 208 cur.right=root; 209 root.left=cur; 210 } 211 if(root.right!=null){ 212 cur=convertBST2DLL(root.right); 213 while(cur.left!=null) 214 cur=cur.left; 215 cur.left=root; 216 root.right=cur; 217 } 218 return root; 219 } 220 //迭代 二叉查找树转为有序的双向链表 仅仅调节指针 221 //todo 222 public static TreeNode convertBST2DLLByLoop(TreeNode root){ 223 if(root==null) 224 return null; 225 TreeNode head=null,cur=root,pre=null; 226 Stack<TreeNode> stack=new Stack<>(); 227 228 while(!stack.isEmpty()||cur!=null){ 229 while(cur!=null){ 230 stack.push(cur); 231 cur=cur.left; 232 } 233 if(!stack.isEmpty()){ 234 cur=stack.pop(); 235 if(head==null) 236 head=cur; 237 if(pre!=null){ 238 pre.right=cur; 239 cur.left=pre; 240 } 241 pre=cur; 242 cur=cur.right; 243 } 244 } 245 return head; 246 } 247 248 //递归求二叉树的第k层的节点个数 249 public static int getNodeNumKthLevelByRecursion(TreeNode root,int k){ 250 if(root==null||k<1) 251 return 0; 252 if(k==1) 253 return 1; 254 return getNodeNumKthLevelByRecursion(root.left,k-1)+getNodeNumKthLevelByRecursion(root.right,k-1); 255 } 256 //迭代求二叉树的第k层的节点个数 257 public static int getNodeNumKthLevelByLoop(TreeNode root,int k){ 258 if(root==null) 259 return 0; 260 Queue<TreeNode> queue=new LinkedList<>(); 261 queue.add(root); 262 263 int i=1; 264 int currentLevelNodes=1; 265 int nextLevelNodes=0; 266 267 while(!queue.isEmpty()&&i<k){ 268 TreeNode cur=queue.remove(); 269 currentLevelNodes--; 270 if(cur.left!=null){ 271 queue.add(cur.left); 272 nextLevelNodes++; 273 } 274 if(cur.right!=null){ 275 queue.add(cur.right); 276 nextLevelNodes++; 277 } 278 if(currentLevelNodes==0){ 279 currentLevelNodes=nextLevelNodes; 280 nextLevelNodes=0; 281 i++; 282 } 283 } 284 return currentLevelNodes; 285 } 286 287 //递归求二叉树的叶子节点个数 288 public static int getNodeNumLeafByRecursion(TreeNode root){ 289 if(root==null) 290 return 0; 291 if(root.left==null&&root.right==null) 292 return 1; 293 return getNodeNumLeafByRecursion(root.left)+getNodeNumLeafByRecursion(root.right); 294 } 295 //迭代求二叉树的叶子节点个数 基于Level order traversal 296 public static int getNodeNumLeafByLoop(TreeNode root){ 297 if(root==null) 298 return 0; 299 Queue<TreeNode> queue=new LinkedList<>(); 300 queue.add(root); 301 302 int leafNodes=0; 303 while(!queue.isEmpty()){ 304 TreeNode cur=queue.remove(); 305 if(cur.left!=null) 306 queue.add(cur.left); 307 if(cur.right!=null) 308 queue.add(cur.right); 309 if(cur.left==null&&cur.right==null) 310 leafNodes++; 311 } 312 return leafNodes; 313 } 314 315 //递归判断两个二叉树是否一样 316 public static boolean isSameTreeByRecursion(TreeNode r1,TreeNode r2){ 317 if(r1==null&&r2==null) 318 return true; 319 if(r1==null||r2==null) 320 return false; 321 if(r1.val!=r2.val) 322 return false; 323 return isSameTreeByRecursion(r1.left,r2.left)&&isSameTreeByRecursion(r1.right,r2.right); 324 } 325 //迭代判断两个二叉树是否一样 326 public static boolean isSameTreeByLoop(TreeNode r1,TreeNode r2){ 327 if(r1==null&&r2==null) 328 return true; 329 if(r1==null||r2==null) 330 return false; 331 Stack<TreeNode> stack1=new Stack<>(); 332 Stack<TreeNode> stack2=new Stack<>(); 333 stack1.push(r1); 334 stack2.push(r2); 335 336 while(!stack1.isEmpty()&&!stack2.isEmpty()){ 337 TreeNode n1=stack1.pop(); 338 TreeNode n2=stack2.pop(); 339 if(n1==null&&n2==null) 340 continue; 341 else if(n1!=null&&n2!=null&&n1.val==n2.val){ 342 stack1.push(n1.right); 343 stack1.push(n1.left); 344 stack2.push(n2.right); 345 stack2.push(n2.left); 346 } 347 else 348 return false; 349 } 350 return true; 351 } 352 353 //递归判断二叉树是否为平衡二叉树 354 public static boolean isAVLByRecursion(TreeNode root){ 355 if(root==null) 356 return true; 357 if(Math.abs(getDepthByRecursion(root.left)-getDepthByRecursion(root.right))>1) 358 return false; 359 return isAVLByRecursion(root.left)&&isAVLByRecursion(root.right); 360 } 361 362 //递归求二叉树的镜像，破坏原有的树 363 public static TreeNode mirrorByRecursion(TreeNode root){ 364 if(root==null) 365 return null; 366 TreeNode left=mirrorByRecursion(root.left); 367 TreeNode right=mirrorByRecursion(root.right); 368 root.left=right; 369 root.right=left; 370 return root; 371 } 372 //迭代求二叉树的镜像，破坏原有的树 373 public static void mirrorByLoop(TreeNode root){ 374 if(root==null) 375 return; 376 Stack<TreeNode> stack=new Stack<>(); 377 stack.push(root); 378 379 while(!stack.isEmpty()){ 380 TreeNode cur=stack.pop(); 381 TreeNode tmp=cur.right; 382 cur.right=cur.left; 383 cur.left=tmp; 384 385 if(cur.left!=null) 386 stack.push(cur.left); 387 if(cur.right!=null) 388 stack.push(cur.right); 389 } 390 } 391 392 //递归求二叉树的镜像，不破坏原有的树 393 public static TreeNode mirrorCopyByRecursion(TreeNode root){ 394 if(root==null) 395 return null; 396 TreeNode newNode=new TreeNode(root.val); 397 newNode.left=mirrorCopyByRecursion(root.right); 398 newNode.right=mirrorCopyByRecursion(root.left); 399 return newNode; 400 } 401 //迭代求二叉树的镜像，不破坏原有的树 402 public static TreeNode mirrorCopyByLoop(TreeNode root){ 403 if(root==null) 404 return null; 405 Stack<TreeNode> stack=new Stack<>(); 406 Stack<TreeNode> newStack=new Stack<>(); 407 stack.push(root); 408 TreeNode newRoot=new TreeNode(root.val); 409 newStack.push(newRoot); 410 411 while(!stack.isEmpty()){ 412 TreeNode cur=stack.pop(); 413 TreeNode newCur=newStack.pop(); 414 415 if(cur.right!=null){ 416 stack.push(cur.right); 417 newCur.left=new TreeNode(cur.right.val); 418 newStack.push(newCur.left); 419 } 420 if(cur.left!=null){ 421 stack.push(cur.left); 422 newCur.right = new TreeNode(cur.left.val); 423 newStack.push(newCur.right); 424 } 425 } 426 return newRoot; 427 } 428 429 //递归判断两棵树是否相互镜像 430 public static boolean isMirrorByRecursion(TreeNode r1,TreeNode r2){ 431 if(r1==null&&r2==null) 432 return true; 433 if(r1==null||r2==null) 434 return false; 435 if(r1.val!=r2.val) 436 return false; 437 return isMirrorByRecursion(r1.left,r2.right)&&isMirrorByRecursion(r1.right,r2.left); 438 } 439 440 //递归求最低公共父节点 441 public static TreeNode getLastCommonParentByRecursion(TreeNode root,TreeNode n1,TreeNode n2){ 442 if(root==null||root==n1||root==n2) 443 return root; 444 TreeNode left=getLastCommonParentByRecursion(root.left,n1,n2); 445 TreeNode right=getLastCommonParentByRecursion(root.right,n1,n2); 446 return left==null?right:right==null?left:root; 447 } 448 //迭代求最低公共父节点 449 //todo 450 public static TreeNode getLastCommonParentByLoop(TreeNode root,TreeNode n1,TreeNode n2){ 451 Map<TreeNode,TreeNode> parent = new HashMap<>(); 452 Deque<TreeNode> stack = new ArrayDeque<>(); 453 parent.put(root,null); 454 stack.push(root); 455 456 while(!parent.containsKey(n1)||!parent.containsKey(n2)){ 457 TreeNode node = stack.pop(); 458 if(node.left!=null){ 459 parent.put(node.left,node); 460 stack.push(node.left); 461 } 462 if(node.right!=null){ 463 parent.put(node.right,node); 464 stack.push(node.right); 465 } 466 } 467 Set<TreeNode> ancestors = new HashSet<>(); 468 while(n1!=null){ 469 ancestors.add(n1); 470 n1=parent.get(n1); 471 } 472 while(!ancestors.contains(n2)) 473 n2=parent.get(n2); 474 return n2; 475 } 476 477 //递归求二叉树节点最大距离 478 public static int getMaxDistanceByRecursion(TreeNode root){ 479 if(root==null) 480 return 0; 481 int k=depth(root.left)+depth(root.right); 482 int left=getMaxDistanceByRecursion(root.left); 483 int right=getMaxDistanceByRecursion(root.right); 484 return Math.max(k,Math.max(left,right)); 485 } 486 private static int depth(TreeNode root){ 487 if(root==null) 488 return 0; 489 return Math.max(depth(root.left),depth(root.right))+1; 490 } 491 492 //递归 由前序遍历序列和中序遍历序列重建二叉树 493 //todo 494 public static TreeNode rebuildBinaryTreeByRecursion(int[] preorder,int[] inorder){ 495 return buildTree(preorder,0,inorder,inorder.length-1,0); 496 } 497 private static TreeNode buildTree(int[] preorder,int idx,int[] inorder,int end,int start){ 498 if(idx>=preorder.length||start>end) 499 return null; 500 TreeNode root = new TreeNode(preorder[idx]); 501 int i; 502 for(i=end;i>=start;i--){ 503 if(preorder[idx]==inorder[i]) 504 break; 505 } 506 root.left=buildTree(preorder,idx+1,inorder,i-1,start); 507 root.right=buildTree(preorder,idx+i-start+1,inorder,end,i+1); 508 return root; 509 } 510 511 //迭代判断二叉树是不是完全二叉树 512 public static boolean isCompleteBinaryTreeByLoop(TreeNode root){ 513 if(root==null) 514 return false; 515 516 Queue<TreeNode> queue=new LinkedList<>(); 517 queue.add(root); 518 boolean mustHaveNoChild=false; 519 boolean result=true; 520 521 while(!queue.isEmpty()){ 522 TreeNode cur=queue.remove(); 523 if(mustHaveNoChild){ 524 if(cur.left!=null||cur.right!=null){ 525 result=false; 526 break; 527 } 528 }else { 529 if(cur.left!=null&&cur.right!=null){ 530 queue.add(cur.left); 531 queue.add(cur.right); 532 }else if(cur.left!=null&&cur.right==null){ 533 mustHaveNoChild=true; 534 queue.add(cur.left); 535 }else if(cur.left==null&&cur.right!=null){ 536 result=false; 537 break; 538 }else{ 539 mustHaveNoChild=true; 540 } 541 } 542 } 543 return result; 544 } 545 546 }
