minStack及tree学习

//实现一个类，实现栈的功能：（构建单链表，有一个头结点，head）

class MinStack {
    private class ListNode {
      int val;
      ListNode next;
      int min;
      ListNode(int x) { val = x; }
    }//leetcode自带的ListNode定义，加入min值，指示从当前值到栈底元素（也就是单链表最后一个节点的值）之间的最小值，
    
    ListNode head=new ListNode(-1);//如果这样定义，那么会默认head.next==null。不用再重复写
    int min;

    public void push(int x) {
        ListNode p=new ListNode(x);        
        if(head==null||head.next==null){
            p.min=x;
        }else{
            p.min=Math.min(head.next.min,x);//每个节点的min表示从该节点到栈底元素中的最小值，在每次插入元素时，都与当前的栈顶元素比较，确定自身携带的min（在之后的getMin函数中不用再进行获取，降低时间复杂度。）
        }
        p.next=head.next;
        head.next=p;
    }

    public void pop() {
        if(head!=null)
            head=head.next;
    }

    public int top() {
        if(head==null||head.next==null)
            return -1;
        int top=head.next.val;
        return top;
    }
    public int getMin() {
        return head.next.min;
    }
}

********************************************************

关于树的题：

//判断两个数是否一模一样sameTree问题，树的问题要擅于使用递归！（开始一直想树的结构由前，中序可以决定，如果得到结果相同，则树一致，但是在遍历中使用递归带来一些麻烦）

public class Solution {
     public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p==null&&q==null)
            return true;
        if((p==null&&q!=null)||(p!=null&&q==null))
            return false;
        if(p.val==q.val){
            if(isSameTree(p.left,q.left)&&isSameTree(p.right,q.right))//判断左子树与右子树是否same
               { return true;}else{
                   return false;
               }
        }
        if(p.val!=q.val)
            return false;
        return true;
     }
}

//我的代码略繁琐：贴上别人的代码：

**********************************************************************************************************
判断树是否对称（注意：对称的树中序遍历结果同样对称）使用递归：
给定的代码格式如下：
public class Solution {
    public boolean isSymmetric(TreeNode root) {
       
    }
想到一颗对称的树必定是首先找到头结点的左右两个节点（p，q），然后p.left==q.right,p.right==q.left，可是看到给定的函数只有一个参数就傻眼了，后来发现可以自己再定义一个函数，传两个节点作为参数，并使用了贴图中的一行简约代码：
public class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root==null) return true;
        if(root.left==null&&root.right==null) return true;
        if((root.left==null&&root.right!=null)||(root.left!=null&&root.right==null))
            return false;
        return ifSym(root.left,root.right);
    }
    
    public static boolean ifSym(TreeNode p,TreeNode q) {
        if(p==null&&q==null) return true;
        if((p==null&&q!=null)||(p!=null&&q==null)) return false;
        if(p.val!=q.val)  return false;
        return (ifSym(p.left,q.right))&&(ifSym(p.right,q.left));
    }
}
**************************************************************************************
用非递归的方式写一下遍历：

minStack及tree学习

原文：http://www.cnblogs.com/litian0605/p/5210079.html