LeetCode.txt

1.树的前序遍历（非递归）：
public class Solution {
    ArrayList<Integer> list = new ArrayList<Integer>();
    public ArrayList<Integer> preorderTraversal(TreeNode root) {
        if(root == null) return list;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode temp = stack.pop();
            list.add(temp.val);
            if(temp.right != null)    
                stack.push(temp.right);   //右子树先进栈，后出栈
            if(temp.left != null)
                stack.push(temp.left);
        }
        return list;
    }
}

2.树的中序遍历（非递归）：
public class Solution{
    ArrayList<Integer> list = new ArrayList<Integer>();
    public ArrayList<Integer> preorderTraversal(TreeNode root){
        if(root == null) return list;
	Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode temp = stack.pop();
            list.add(temp.val);
            if(temp.left != null)    
                stack.push(temp.left);   //左子树先进栈，后出栈
            if(temp.right != null)
                stack.push(temp.right);
        }
        return list;
    }
}

3.树的后序遍历（非递归）：
public class Solution{
    ArrayList<Integer> list = new ArrayList<Integer>();
    public ArrayList<Integer> preorderTraversal(TreeNode root){
        
    }
}


4.链表部分逆转：
{1，2，3，4，5，6}------> {1，6，2，5，3，4}
//快慢指针找到中间节点，将后面的链表反转（前插法），合并链表
public class Solution {
    public void reorderList(ListNode head) {
        if(head==null)
            return;
        ListNode slow=head;
        ListNode fast=head;
        while(fast.next!=null&&fast.next.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        ListNode pre=slow.next;
        if(pre!=null&&pre.next!=null){
            ListNode nex=pre.next;
            while(nex!=null){
            pre.next=nex.next;
            nex.next=slow.next;
            slow.next=nex;
            nex=pre.next;
           }        
        }     
        merge(head,slow);
    }
    public void merge(ListNode head,ListNode slow){
        ListNode p=head;
        ListNode q=slow.next;
        while(q!=null&&p!=null){
            slow.next=q.next;
            q.next=p.next;
            p.next=q;
            q=slow.next;
            p=p.next.next;
        }
    }
}

4.判断二叉树是否是平衡二叉树：
public class Solution {
    //后续遍历时，遍历到一个节点，其左右子树已经遍历  依次自底向上判断，每个节点只需要遍历一次
     
    private boolean isBalanced=true;
    public boolean IsBalanced_Solution(TreeNode root) {
         
        getDepth(root);
        return isBalanced;
    }
    public int getDepth(TreeNode root){
        if(root==null)
            return 0;
        int left=getDepth(root.left);
        int right=getDepth(root.right);
         
        if(Math.abs(left-right)>1){
            isBalanced=false;
        }
        return right>left ?right+1:left+1;
         
    }
}