public static void preOrderUnRecur(Node head) {
        //1先将头结点压入栈
        //2 弹出栈顶元素，再将该节点的左右节点压入栈(先右后左)
        //3 不断重复2 ，直到stack为空
        if (head == null)
            return;
        Stack<Node> stack = new Stack<>();
        stack.push(head);
        while (!stack.isEmpty()) {
            Node cur = stack.pop();
            System.out.println(cur.data + " ");
            if (cur.right != null) {
                stack.push(cur.right);
            }
            if (cur.left != null) {
                stack.push(cur.left);
            }

        }
    }

  public static void midOrderUnrecur(Node head) {
        //1 申请一个栈 cur=head
        // 2 将栈左子树依次压入 cur=cur.left
        // 不断重复2，直到cur==null ，弹出node 并打印，并cur=node.right ，继续重复
        if (head == null)
            return;
        Stack<Node> stack = new Stack<>();
        stack.push(head);
        while (!stack.isEmpty() || head != null) {
            if (head!= null) {
                stack.push(head);
                head = head.left;
            }else{
                Node node=stack.pop();
                System.out.println(node.data);
                head=node.right;
            }

        }
    }

 
    TreeNode prev =null;// 中序遍历这棵树，并保存前驱节点至prev中
    //使用递归
    public boolean isValidBST(TreeNode root){
        if(root != null){
            if(!isValidBST(root.left))
                return false;
            if(prev!=null && root.val<=prev.val){
                return false;
             }
            prev = root;
            return isValidBST(root.right);
        }
        return true;
    }

  /*
     *@description:将二叉树转换为字符串
     * # 表示节点为null ,每个节点以 '!' 分割
     *@params:[head]
     *@return:java.lang.String
     *@author:Mao
     *@date:2019/4/12 8:46
     **/
    public static String seriaByPre(Node head) {
        if (head == null)
            return "#!";
        String res = head.data + "!";
        res += seriaByPre(head.left);
        res += seriaByPre(head.right);
        return res;
    }

    /*
     *@description:反序列化 将str转换为二叉树
     *@params:[str]
     *@return:com.mao.tree.Node
     *@author:Mao
     *@date:2019/4/12 8:53
     **/
    public static Node reconByPre(String str) {
        if (str == null)
            return null;
        //将str 按照'!'分割成数组
        String[] strs = str.split("!");
        Queue<String> queue = new LinkedList<>();
        for (int i = 0; i < strs.length; i++) {
            queue.offer(strs[i]);
        }
        return reconByPreOrder(queue);
    }

    /*
     *@description:前序递归
     *@params:[strs]
     *@return:com.mao.tree.Node
     *@author:Mao
     *@date:2019/4/12 8:59
     **/
    private static Node reconByPreOrder(Queue<String> queue) {
        String value = queue.poll();
        if ("#".equals(value)) {
            return null;
        }
        Node node = new Node(Integer.valueOf(value));
        // 将值与节点的左右子树相连接
        node.left = reconByPreOrder(queue);
        node.right = reconByPreOrder(queue);
        return node;
    }

  //层序遍历
    public static String seriaByLevel(Node node) {
        if (node == null)
            return "#!";
        String res = node.data + "!";
        Queue<Node> queue = new LinkedList<Node>();
        queue.offer(node);
        while (!queue.isEmpty()) {
            Node head = queue.poll();
            if (head.left != null) {
                res += head.left.data + "!";
                queue.offer(head.left);
            } else {
                res += "#!";
            }
            if (head.right != null) {
                res += head.right.data + "!";
                queue.offer(head.right);
            } else {
                res += "#!";
            }
        }
        return res;
    }

    /*
     *@description:层序遍历反序列化
     *@params:[args]
     *@return:void
     *@author:Mao
     *@date:2019/4/12 9:55
     **/
    public static Node reconByLevel(String str) {
        if (str == null)
            return null;
        String[] strs = str.split("!");
        int index = 0;
        Node head = generatedNode(strs[index++]);
        Queue<Node> queue = new LinkedList<>();
        queue.offer(head);
        Node node = null;
        while (!queue.isEmpty()&& index!=strs.length) {
            node = queue.poll();
            node.left = generatedNode(strs[index++]);
            node.right = generatedNode(strs[index++]);
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }

        }
        return head;
    }

    private static Node generatedNode(String str) {
        if ("#".equals(str)) {
            return null;
        }
        return new Node(Integer.valueOf(str));
    }

   public static boolean contains(Node t1,Node t2){
		//需检查t1 是否为null 为null则停止
        if(t1==null){
            return false;
        }
        return check(t1,t2)|| contains(t1.left,t2)|| contains(t1.right,t2);
    }

    private static boolean check(Node tt1, Node tt2) {
        if(tt2==null){
            return true;
        }
        if(tt1==null || tt2.data!=tt1.data){
            return false;
        }
        return check(tt1.left,tt2.left) && check(tt1.right,tt2.right);
    }

	public Node generateTree(int[] sortArr) {
		if (sortArr == null)
			return null;
		return generate(sortArr, 0, sortArr.length - 1);
	}

	private Node generate(int[] sortArr, int start, int end) {
		if (start > end)
			return null;
		int mid = (start + end) / 2;
		Node head = new Node(sortArr[mid]);
		head.left = generate(sortArr, start, mid - 1);
		head.right = generate(sortArr, mid + 1, end);

		return head;
	}

   public Node preInToTree(int[] preArr,int[] midArr){
        if(preArr==null || midArr==null){
            return null;
        }
        //使用HashMap将midArr数组存储
        HashMap<Integer,Integer> map=new HashMap<>();
        for (int i=0;i<midArr.length;i++){
            map.put(midArr[i],i);
        }
        return  preTree(preArr,0,preArr.length-1,midArr,0,midArr.length-1,map);
    }
    private Node preTree(int[] preArr, int preStart, int preEnd, int[] midArr, int midStart, int midEnd, Map<Integer,
                Integer> map) {
            if (preStart> preEnd){
                return null;
            }
            Node head=new Node(preArr[preStart]);
            int index=map.get(preArr[preStart]);
            head.left=preTree(preArr,preStart+1,preStart+midEnd-index,midArr,midStart,index-1,map);
            head.right=preTree(preArr,preStart+index-midStart+1,midEnd,midArr,index+1,midEnd,map);
            return head;
    }

  public Node inPosToTree(int[] mid,int[] pos){
        if(mid==null || pos==null){
            return null;
        }
        HashMap<Integer,Integer> map=new HashMap<>();
        for (int i=0;i<mid.length;i++){
            map.put(mid[i],i);
        }
        return posToTree(pos,0,pos.length-1,mid,0,mid.length-1,map);
    }

    private Node posToTree(int[] pos, int posStart, int posEnd, int[] mid, int midStart, int midEnd,
                           HashMap<Integer, Integer> map) {
        if(posStart>posEnd){
            return null;
        }
        int arr=pos[posEnd];
        int index=map.get(arr);
        Node node=new Node(arr);
        node.left=posToTree(pos,posStart,posStart+index-midStart-1,mid,midStart,index-1,map);
        node.right=posToTree(pos,posStart+index-midStart,posEnd-1,mid,index+1,midEnd,map);
        return node;
    }
    public static void main(String[] args) {
        int[] pos=new int[]{4,5,2,6,7,3,1};
        int[] in=new int[]{4,2,5,1,6,3,7};
        InPosToTree test=new InPosToTree();
        Node head=test.inPosToTree(in,pos);
        test.pre(head);
    }
    public void pre(Node head){
        if (head==null)
            return;
        System.out.print(head.data);
        pre(head.left);
        pre(head.right);
    }

//boolean res 相当于全局变量
/* 当不满足时立刻返回
	if(!res[0])
	{
      return level;
    }
  */

public static boolean isBanlance(Node head){
        boolean[] res=new boolean[1];
        res[0]=true;
        System.out.println("height:"+getHeight(head,1,res));
        return res[0];
    }

    private static int getHeight(Node head, int level, boolean[] res) {
        if(head==null)
            return level;
       int lh= getHeight(head.left,level+1,res);
        if(!res[0]){
            return level;
        }
        int rh=getHeight(head.right,level+1,res);
        if(!res[0])
            return level;
        if(Math.abs(lh-rh)>1){
            res[0]=false;
        }
        return Math.max(lh,rh);
    }

    public static void main(String[] args) {
        String str = "1!2!#!4!#!#!#!";
        Node head = reconByLevel(str);
        System.out.println( isBanlance(head));
    }

public class IsPostArray {
    public boolean isPostArray(int[] arrs){
        if(arrs==null ||arrs.length==0)
            return false;
        return  isPost( arrs, 0 , arrs.length-1);
    }
    private boolean isPost(int[] arrs, int start, int end) {

        // 整个递归的终止条件
        if(start==end){
            return true;
        }
        int less=-1; //找到左子树右边界临界点
        int more=end; //找到右子树最左边
        //找到左子树的右边界，右子树的左边界
        for(int i=start;i<end;i++){
            if(arrs[end]>arrs[i]){
                less=i;
            }else {
                //找到第一个比根节点大的索引
                more=more==end?i:more;
            }
        }
        //只存在左子树或只存在右子树
        if(less==-1 || more==end){
            return isPost(arrs,start,end-1);
        }
        //若左边界和右边界-1 相等 则继续遍历，不等直接返回false
        if(less!=more-1){
            return false;
        }
        //进行左子树和右子树的遍历
        return isPost(arrs,start,less)&& isPost(arrs,more,end-1);
    }
}

    public Node postArrayToBST(int[] arrs){
        if(arrs==null)
            return null;
        return  posToBST(arrs,0,arrs.length-1);
    }
    private Node posToBST(int[] arrs, int start, int end) {
            if(start>end)
                return null;
            int less=-1;
            int more=end;
            Node node=new Node(arrs[end]);
            for (int i=0;i<arrs.length;i++){
                if(arrs[end]>arrs[i]){
                    less=i;
                }else {
                    more=more==end?i:more;
                }
            }
            node.left=posToBST(arrs,start,less);
            node.right=posToBST(arrs,more,end);
            return node;
    }

    public boolean isCBT(Node head){
          if(head==null)
              return false;
          Queue<Node> queue=new LinkedList<>();
  
          boolean leaf=true;
          Node left=null;
          Node right=null;
  
          queue.offer(head);
          while(!queue.isEmpty()){
              head=queue.poll();
              left=head.left;
              right=head.right;
              
              if(leaf &&(left!=null || right!=null) || (left==null&&right!=null)){
                  return false;
              }
              if(left!=null){
                  queue.offer(left);
              }
              if(right!=null){
                  queue.offer(right);
              }else{
                  leaf=true;
              }
          }
          return true;
      }

 public boolean isValidBST(TreeNode root) {
          Stack<TreeNode> stack=new Stack();
        double inOrder=-Double.MAX_VALUE;
        while(!stack.isEmpty() || root!=null){
            while(root!=null){
                stack.push(root);
                root=root.left;
            }
            root=stack.pop();
            if(root.val<=inOrder){
                return false;
            }
            inOrder=root.val;
            root=root.right;
        }
        return true;
    }

public boolean isValidBST(TreeNode root) {
          Stack<TreeNode> stack=new Stack();
        double inOrder=-Double.MAX_VALUE;
        while(!stack.isEmpty() || root!=null){
           if(root!=null){
                stack.push(root);
                root=root.left;
            }else{
            root=stack.pop();
            if(root.val<=inOrder){
                return false;
            }
            inOrder=root.val;
            root=root.right;
           }
        }
        return true;
    }

public class GenerateBSTByOrderArr {
    public static Node generateBST(int[] arr){
        if(arr==null){
            return  null;
        }
        return  getBst(arr,0,arr.length-1);   
    }
    /*
    *@description: 使用递归生成平衡搜索二叉树
    *@params:[arr, i, i1]
    *@return:com.mao.tree.Node
    *@author:Mao
    *@date:2019/4/23 8:31
    **/
    private static Node getBst(int[] arr, int start, int end) {
        if(start> end){
            return null;
        }
        int mid=(start+end)/2;
        Node node=new Node(arr[mid]);
        node.left=getBst(arr,start,mid-1);
        node.right=getBst(arr,mid+1,end);
        return node;
    }

      //使用后序遍历
        /*
            1
          /  \
         2     3
       / \    / \
      4   5  6   7
                /
               8
         */
    public Node lowestAncestors(Node head,Node o1,Node o2){
        if(head==null || head==o1 || head==o2){
            return head;
        }
        Node left=lowestAncestors(head.left,o1,o2);
        Node right=lowestAncestors(head.right,o1,o2);
        if(left!=null && right!=null){
            return head;
        }
        //若其中有一个为null 不为null记为node 
        //说明node要么是o1 要么是o2 
        //或者 是o1 和o2的最近祖先
        return left!=null?left:right;
    }

start = i == 0 || chars[i - 1] == ' ' ? i : start;
end = i == chars.length - 1 || chars[i + 1] == ' ' ? i : end;

	while (!s1.isEmpty()) {
			int tmp = s1.pop();
        	// 此处不能有等于 会无限循环
			while (!s2.isEmpty() && tmp < s2.peek()) {
				s1.push(s2.pop());
			}
			s2.push(tmp);
		}

public static Node removeLastKthNode(Node head, int k,int length) {
		if (head == null) {
			return head;
		}
		Node cur = head;
		int k2=k;
		while (cur != null) {
			cur = cur.next;
			k--;
		}
		Node cur2 = head;
		if (k < 0) {
			int tmp=k2-length;
			//直接使用K  while(++k!=o)
			while (tmp++ != 0) {
				cur2 = cur2.next;
			}
			Node next = cur.next;
			cur2.next = next.next;
			next.next = null;
			return head;

		} else
		if (k == 0) {
			head = head.next;
			return head;
		} else {
			return head;
		}

public static Node removeMiddleNode(Node node) {
		if (node == null) {
			return node;
		}
		if (node.next.next == null) {
			return node.next;
		}
		Node pre = node;
		Node cur = node.next.next;
		while (cur.next != null && cur.next.next != null) {

			pre = pre.next;
			cur = cur.next.next;

		}
		pre.next = pre.next.next;
		return node;
	}

public static DoubleNode reverseDouble(DoubleNode node) {
		DoubleNode next = null;
		DoubleNode pre = null;
		while (node != null) {
			next = node.next;
			node.next = pre;
			node.pre = next;
			pre = node;
			node = next;
		}		
		return pre;

	public static Node partReverse(Node head, int from, int to) {
		// 找到要反转节点的前一个节点，且不是头结点
		int i = 0;
		Node h1 = head;
		Node preFrom = null;
		Node postTo = null;
		// 获得链表from前一个preFrom.to的后一个postTo
		while (h1 != null) {
			i++;
			preFrom = i == from - 1 ? h1 : preFrom;
			postTo = i == to + 1 ? h1 : postTo;
			h1 = h1.next;
		}		
		//拿到要反转的第一个节点
		h1 = preFrom == null ? head : preFrom.next;	
		//连接翻转后的尾节点	
		Node h2 = h1.next;
		h1.next = postTo;
		// 反转节点
		Node next = null;
		int j = to - from;
		while (h2 != postTo) {
			next = h2.next;
			h2.next = h1;
			h1 = h2;
			h2 = next;
		}
		// h1.next = pre;
		if (preFrom != null) {
			preFrom.next = h1;
			// 返回旧节点
			return head;
		}
		// 返回新节点
		return h1;
	}

    val1=s1.isEmpty()?0:s1.pop();
    val2=2.isEmpty()?0:s2.pop();
	val3=val1+val2+cal;
	cal=val3/10; //进位
    pre=cur;
	cur=new Node(cal%10);
	cur.next=pre;

     	pre = cur;
		cur = new Node(val3);
		cur.next = pre;

public static Node addList1(Node head1, Node head2) {
		if (head1 == null || head2 == null) {
			return head1 == null ? head1 : head2;
		}
		Stack<Integer> s1 = new Stack<Integer>();
		Stack<Integer> s2 = new Stack<Integer>();
		while (head1 != null || head2 != null) {
			if (head1 != null) {
				s1.push(head1.data);
				head1 = head1.next;
			}
			if (head2 != null) {
				s2.push(head2.data);
				head2 = head2.next;
			}
		}
		Node pre = null;
		Node cur = null;
		int val1 = 0;
		int val2 = 0;
		int cal = 0;
		while (!s1.isEmpty() || !s2.isEmpty()) {

			if(!s1.isEmpty()){
				val1 = s1.pop();
			} else {
				val1 = 0;
			}
			if(!s2.isEmpty()){
				val2=s2.pop();
			} else {
				val2 = 0;
			}

			int val3 = val1 + val2 + cal;
			if (val3 >= 10) {
				cal = 1;
				val3 = val3 % 10;
			} else {
				cal = 0;
			}
			pre = cur;
			cur = new Node(val3);
			cur.next = pre;
		}
		// 当两个栈都为空，且还存在进位时
		if (cal == 1) {
			Node n = new Node(cal);
			n.next = cur;
			return n;
		}

		return cur;
	}

public static Node removeRepeat(Node head) {
		if(head==null)
			return null;
		HashMap<Integer, Integer> map=new HashMap<Integer, Integer>();
		map.put(head.data, 1);
		Node n1 = head;
		Node pre = head;
		Node cur = head.next;
		while (cur != null) {
			if (map.containsKey(cur.data)) {
				pre.next = cur.next;
				cur = cur.next;

			} else {
				map.put(cur.data, 1);
				pre = cur;
				cur = cur.next;
			}


		}
		return n1;
	}

 stack.peek().next=head;
 head=stack.pop();

//直接删除
public static Node removeSpecialValue(Node head, int num) {
		if(head==null)
			return head;
		Node h = head;
		Node pre = head;
		Node cur = head.next;
		while (cur != null) {
			if (cur.data == num) {
				pre.next = cur.next;
			} else {
				pre = pre.next;
			}
			cur = cur.next;
		}
		return h;
	}

//使用栈
public static Node removeSpecialValueByStack(Node head, int num) {
		Stack<Node> s = new Stack<Node>();
		while (head != null) {
			if (head.data != num) {
				s.push(head);
			}
			head = head.next;
		}
		Node pre = null;
		Node cur = null;
		while (!s.isEmpty()) {
			cur = s.pop();
			cur.next = pre;
			pre = cur;
		}	
		return cur;
	}

// 获得最小节点的前一个节点
	private static Node getSmallPre(Node head) {
		Node smallPre = null;
		Node small = head;
		Node pre = head;
		Node cur = head.next;

		while (cur != null) {
			if(cur.data<pre.data){
				smallPre=pre;
				small = cur;
			}
			pre = cur;
			cur = cur.next;

		}
		return smallPre;
	}

//经典实现
public static Node insertByCircle2(Node head, Node num) {
		if (head == null) {
			num.next = num;
			return num;
		}

		Node pre = head;
		Node cur = head.next;
		while (cur != head) {
			if (pre.data <= num.data && num.data <= cur.data) {
				break;
			}
			pre = cur;
			cur = cur.next;
		}
		pre.next = num;
		num.next = cur;
		return head.data > num.data ? num : head;
	}

//自己实现
public static Node insertByCircle(Node head, Node num) {
		if (head == null)
			return null;

		
		Node cur = head;
		Node tail = null;
		// 获取taile节点
		while (cur.next != head) {
			cur = cur.next;
		}
		tail = cur;
		cur = tail.next;
		while (cur != tail) {
			if (cur.data >= num.data && cur.next.data <= num.data) {
				//插入节点
				Node next=cur.next;
				cur.next=num;
				num.next=next.next;
						
			}
			cur = cur.next;

		}
		if (num.data < head.data ) {
			tail.next = num;
			num.next = head;
			head = num;
		}
		if (num.data > tail.data) {
			tail.next=num;
			num.next=head;
			tail = num;
		}
		return head;
	}

public static Node merge(Node head1, Node head2) {
		if (head1 == null || head2 == null) {
			return head1 == null ? head2 : head1;
		}
		// 头结点为两个中最小的一个
		Node head = head1.data < head2.data ? head1 : head2;
		Node cur1 = head == head1 ? head1 : head2;
		Node cur2 = head == head1 ? head2 : head1;
		Node pre=null;
    	//书上 Node next=null;
		while (cur1 != null && cur2 != null) {
			if(cur1.data<cur2.data){
				pre=cur1;
				cur1 = cur1.next;
			} else {
				Node next = cur2.next;
				pre.next = cur2;
				cur2.next = cur1;
				cur2 = next;
				pre = cur2;
			}
		}

		pre.next = cur1 == null ? cur2 : cur1;
		return head;

	}

  public static Node relocate(Node head){
        if(head==null)
            return null;
        //将链表划分左右两半区
        Node mid=head;
        Node right=head.next;
        while(right.next!=null && right.next.next!=null){
            mid=mid.next;
            right=right.next.next;
        }
        System.out.println("node:"+mid.next.data);
        Node cur=head;
        right=mid.next;
      // 标准写法 
      // mid.next=null;
      //while(cur.next!=null)
        while(cur!=mid){
            Node next_left=cur.next;
            Node next_right=right.next;
            cur.next=right;
            right.next=next_left;
            right=next_right;
            cur=next_left;
        }
        cur.next=right;
        return head;
    }

public class UniquePath{
    
    public int uniquePath(int m,int n){
        int[][] res=new int[m-1][n-1];
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
               if(i==0 ||j==0){
                    res[i][j]=1;
                }else{
                     res[i][j]=res[i-1][j]+res[i][j-1];
                }
            }
        }
        return res[m-1][n-1];
    }
    
}

public class UniquePath{
  
     public int uniquePaths(int m, int n) {
        int[][] memo=new int[m][n];
        return dfs(m-1,n-1,memo);
    }
    public int dfs(int m,int n,int[][] memo){
        if(memo[m][n]!=0){
            return memo[m][n];
        }
        if( m==0 || n==0){
            return 1;
        }
        memo[m][n]=dfs(m-1,n,memo)+dfs(m,n-1,memo);
        return memo[m][n];
    }
}

 public int fib(int n){
        int[] memo=new int[n+1];
        return  cal(n,memo);
    }
    private  int cal(int n ,int[] memo){
        if(n==0)
            return 0;
        if(n==1){
            return 1;
        }
        if(memo[n]!=0){
            return memo[n];
        }
        return cal(n-1,memo)+cal(n-2,memo);
    }

    public static void main(String[] args) {
        Fibonacci sol=new Fibonacci();
        System.out.println(sol.fib(4));
    }

 //暴力破解 时间复杂度为O(n2)
    public int maxProfit(int[] prices) {
        int max=0;
        for(int i=0;i<prices.length;i++){
            for (int j=i+1;j<prices.length;j++){
                int tmp=prices[j]-prices[i];
                if (tmp>max){
                    max=tmp;
                }

            }
        }
        return max;
    }
    //时间复杂度为O(n)
    public int maxProfit2(int[] prices){
        int minPrice=Integer.MAX_VALUE; //最低价格
        int maxPro=0;//最大利润
        for (int i=0;i<prices.length;i++){
            if(prices[i]<minPrice){
                minPrice=prices[i];
            }else if(prices[i]-minPrice>maxPro){
                maxPro=prices[i]-minPrice;
            }
        }
        return maxPro;
    }
    //考虑使用动态规划？？
    public int maxProfit3(int[] prices) {
        if(prices.length == 0 || prices.length == 1) return 0;

        int maxProfit = 0;
        int min = prices[0];

        for(int i = 0; i < prices.length; i++) {
            min = Math.min(min, prices[i]);
            maxProfit = Math.max(maxProfit, prices[i] - min);
        }

        return maxProfit;
    }