算法训练——栈算法（LeetCodeHOT100）

摘要

堆栈算法

一、二叉树的中序遍历

94. 二叉树的中序遍历

package 栈算法;

import java.util.*;

public class inorderTraversal94 {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public List inorderTraversal(TreeNode root) {
        List res = new ArrayList();
        Deque stk = new LinkedList();
        // 递归判断
        while (root != null || !stk.isEmpty()) {
            while (root != null) {
                stk.push(root);
                // 递归进左边
                root = root.left;
            }
            //
            root = stk.pop();
            res.add(root.val);
            root = root.right;
        }
        return res;
    }

    public List inorderTraversal2(TreeNode root) {
        ArrayList list = new ArrayList();
        Stack stack = new Stack();
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.add(root);
                root = root.left;
            }
            root = stack.pop();
            // 加入节点数值
            list.add(root.val);
            root = root.right;
        }
        return list;
    }
}

20. 有效的括号

package 栈算法;

import org.junit.Test;

import java.util.HashMap;
import java.util.Stack;

public class isValid20 {
    /**
     * 是否有效
     *
     * @param s
     * @return
     */
    public boolean isValid(String s) {
        HashMap map = new HashMap();
        map.put('}', '{');
        map.put(')', '(');
        map.put(']', '[');

        Stack stack = new Stack();

        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '{' || s.charAt(i) == '[' || s.charAt(i) == '(') {
                stack.add(s.charAt(i));
            }else {
                if (!stack.isEmpty() && stack.peek() == map.get(s.charAt(i))) {
                    stack.pop();
                } else {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }

    @Test
    public void test() {
        boolean valid = isValid("([)]");
        System.out.println(valid);

    }
}

155. 最小栈

package 栈算法;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Stack;

public class MinStack155 {
    /**
     * 最小栈
     */

    Stack stack;
    public MinStack155() {
        stack=new Stack();
    }

    public void push(int val) {
        if (stack.isEmpty()) {
            stack.add(val);
            stack.add(val);
        } else {
            int value=stack.peek();
            if (value>=val){
                stack.add(val);
                stack.add(val);
            }else {
                stack.add(val);
                stack.add(value);
            }
        }
    }

    public void pop() {
        stack.pop();
        stack.pop();
    }

    public int top() {
        int n1=stack.pop();
        int n2=stack.pop();
        stack.add(n2);
        stack.add(n1);
        return n2;
    }

    public int getMin() {
        int tmp=stack.peek();
        return tmp;
    }
}

234. 回文链表

import org.junit.Test;

import java.util.*;
import java.util.stream.Collectors;


public class test {

    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    /**
     * 判断是否为回文链表 将数据拷贝到数组和list中 在采用的双指针的方式来判断的
     *
     *
     *
     * @param head
     * @return
     */
    public boolean isPalindrome(ListNode head) {
        List list = new ArrayList();
        while (head != null) {
            list.add(head.val);
            head = head.next;
        }
        int [] arr=new int[list.size()];
        for (int i=0;i