剑指offer07-09

1.重建二叉树

方法1：

 1 public static TreeNode buildTree(int[] preorder,int[] inorder){
 2         //非递归的方法
 3         Stack<TreeNode> stack = new Stack<>();
 4         int index = 0;
 5         TreeNode tempNode = null;
 6 
 7 
 8 
 9         while(index<preorder.length){
10             if(stack.empty()){
11                 stack.push(new TreeNode(preorder[index]));
12                 index++;
13                 continue;
14             }else{
15                 tempNode = stack.peek();
16                 stack.push(new TreeNode(preorder[index]));
17 
18                 if(getIndex(inorder,tempNode.val)<getIndex(inorder,preorder[index])){
19                     System.out.println("父节点："+tempNode.val+"右孩子："+stack.peek().val);
20                     tempNode.right = new TreeNode(preorder[index]);
21                 }else{
22                     System.out.println("父节点："+tempNode.val+"左孩子："+stack.peek().val);
23                     tempNode.left = new TreeNode(preorder[index]);
24                 }
25             }
26 
27             if(getIndex(inorder,stack.peek().val)==0&&getIndex(preorder,inorder[getIndex(inorder,stack.peek().val)+1])<index){
28                 System.out.println("节点"+stack.peek().val+"出栈");
29                 stack.pop();
30 
31             }
32             else if(getIndex(inorder,stack.peek().val)==inorder.length-1&&getIndex(preorder,inorder[getIndex(inorder,stack.peek().val)-1])<index) {
33                 System.out.println("节点"+stack.peek().val+"出栈");
34                 stack.pop();
35 
36             }
37             else if(getIndex(preorder,inorder[getIndex(inorder,stack.peek().val)+1])<index||getIndex(preorder,inorder[getIndex(inorder,stack.peek().val)-1])<index) {
38                 System.out.println("节点"+stack.peek().val+"出栈");
39                 stack.pop();
40             }
41             index ++;
42 
43         }
44         while(stack.size()>1) stack.pop();
45         TreeNode root = stack.pop();
46         //TreeNode root = null;
47         System.out.println(root.val);
48         return root;
49     }
50 
51     public static int getIndex(int[] arr,int target){
52         for (int i = 0; i < arr.length; i++) {
53             if(arr[i] == target) return i;
54         }
55         return -1;
56     }

2.用两个栈来实现队列

方法1：

 1 class CQueue{
 2 
 3     // 用两个栈来实现队列
 4     Stack<Integer> stackFirst;
 5     Stack<Integer> stackSecond;
 6 
 7     public CQueue(){
 8         stackFirst = new Stack<>();
 9         stackSecond = new Stack<>();
10 
11 
12     }
13 
14     public void appendTail(int value){
15         stackFirst.push(value);
16     }
17 
18     public int deleteHead(){
19         if(stackFirst.empty()) return -1;
20         while(!stackFirst.empty()) stackSecond.push(stackFirst.pop());
21         int re = stackSecond.pop();
22         while(!stackSecond.empty()) stackFirst.push(stackSecond.pop());
23         return re;
24     }
25 }

第一栈用来存放数据，第二个栈用来辅助，当需要对队首操作时就将第一栈中的数据分别pop，然后push到第二个栈里面，然后处理。

知之为知之，不知为不知