<剑指offer> 剑指offer 07.09

摘要：
07 重建二叉树
09 用两个栈实现队列

面试题07 重建二叉树

题目：

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

解析：

• 递推参数： 前序遍历中根节点的索引pre_root、中序遍历左边界in_left、中序遍历右边界in_right
• 终止条件： 当 in_left > in_right ，子树中序遍历为空，说明已经越过叶子节点，此时返回 nullnull 。
• 递推工作：

1.立根节点root： 值为前序遍历中索引为pre_root的节点值。
2.搜索根节点root在中序遍历的索引i
3.构建根节点root的左子树和右子树： 通过调用 recur() 方法开启下一层递归
——左子树： 根节点索引为 pre_root + 1 ，中序遍历的左右边界分别为 in_left 和 i - 1。
——右子树： 根节点索引为 i - in_left + pre_root + 1（即：根节点索引 + 左子树长度 + 1），中序遍历的左右边界分别为 i + 1 和 in_right。

• 返回值： 返回 root，含义是当前递归层级建立的根节点 root 为上一递归层级的根节点的左或右子节点。

  解法：

  //java解法
  /**
   * Definition for a binary tree node.
   * public class TreeNode {
   *     int val;
   *     TreeNode left;
   *     TreeNode right;
   *     TreeNode(int x) { val = x; }
   * }
   */
  class Solution {
      HashMap<Integer,Integer> map=new HashMap<>();
      int[] preNode;
      public TreeNode buildTree(int[] preorder, int[] inorder) {
              preNode=preorder;
              for(int i=0;i<inorder.length;i++){
                  map.put(inorder[i],i);
              }
              return recur(0,0,inorder.length-1);
      }
      TreeNode recur(int pre_root,int in_left,int in_right){
              if(in_left>in_right){
                  return null;
              }
              int idx=map.get(preNode[pre_root]);
              TreeNode root=new TreeNode(preNode[pre_root]);
              // 左子树递归
              root.left=recur(pre_root+1,in_left,idx-1);
              // 右子树递归
              root.right=recur(idx-in_left+pre_root+1,idx+1,in_right);
              return root;
      }
  }

  #python解法
  # Definition for a binary tree node.
  # class TreeNode:
  #     def __init__(self, x):
  #         self.val = x
  #         self.left = None
  #         self.right = None
  
  class Solution:
      def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
          self.inNode,self.HashMap=preorder,{}
          for i in range(len(inorder)):
              self.HashMap[inorder[i]]=i
          return self.recur(0,0,len(inorder)-1)
      def recur(self,pre_root:int,in_left:int,in_right:int) ->TreeNode:
          if in_left>in_right: return
          root=TreeNode(self.inNode[pre_root])
          idx=self.HashMap[self.inNode[pre_root]]
          root.left=self.recur(pre_root+1,in_left,idx-1)
          root.right=self.recur(idx-in_left+pre_root+1,idx+1,in_right)
          return root

面试题09 用两个栈实现队列

题目:

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

解法：

普通思路一：

一个栈存储元素，一个栈辅助，每次添加元素时利用两个栈将顺序调整为队列“先进先出”的形式；

class CQueue {
//用栈实现队列
    Stack<Integer> s1=new Stack<>();
    Stack<Integer> s2=new Stack<>();
    int size=0;
    public CQueue() {

    }
    
    public void appendTail(int value) {
        while(!s1.isEmpty()){
            s2.push(s1.pop());
        }
        s1.push(value);
        size++;
        while(!s2.isEmpty()){
            s1.push(s2.pop());
        }
    }
    
    public int deleteHead() {
        if(s1.isEmpty()){
            return -1;
        }
        size--;
        return s1.pop();
    }
//通过两个LinkedList实现队列
	LinkedList<Integer> s1=new LinkedList<>();
    LinkedList<Integer> s2=new LinkedList<>();
    public CQueue() {

    }
    
    public void appendTail(int value) {
        while(!s1.isEmpty()){
            s2.add(s1.removeLast());
        }
        s1.add(value);
        while(!s2.isEmpty()){
            s1.add(s2.removeLast());
        }
    }
    
    public int deleteHead() {
        if(s1.isEmpty()){
            return -1;
        }
        return s1.removeLast();
    }
}

class CQueue:
    def __init__(self):
        self.s1,self.s2=[],[]
    def appendTail(self, value: int) -> None:
        while self.s1:
            self.s2.append(self.s1.pop())
        self.s1.append(value)
        while self.s2:
            self.s1.append(self.s2.pop())

    def deleteHead(self) -> int:
        if self.s1:
           return self.s1.pop()
        return -1

优化思路二：

在删除队列元素时，利用两个栈实现队列：
利用A栈添加元素，B专用于栈弹出元素；

class CQueue {
    LinkedList<Integer> A, B;
    public CQueue() {
        A = new LinkedList<Integer>();
        B = new LinkedList<Integer>();
    }
    public void appendTail(int value) {
        A.add(value);
    }
    public int deleteHead() {
        if(!B.isEmpty()) return B.removeLast();
        if(A.isEmpty()) return -1;
        while(!A.isEmpty())
            B.add(A.removeLast());
        return B.removeLast();
    }
}

class CQueue:
    def __init__(self):
        self.A, self.B = [], []

    def appendTail(self, value: int) -> None:
        self.A.append(value)

    def deleteHead(self) -> int:
        if self.B: return self.B.pop()
        if not self.A: return -1
        while self.A:
            self.B.append(self.A.pop())
        return self.B.pop()