Tree and Stack LEETCODE-100-DAY10

题型技巧总结：栈▼;)

8-1 常考题型1 - 平衡符号 (括号匹配)

• 栈的实现：顺序栈、链式栈
• Parentheses(){}[]

20.

class Solution {
    public boolean isValid(String s) {
        if (s.isEmpty())
            return true;
        Stack<Character> stack  = new Stack<Character>();
        for (char c:s.toCharArray()) {
            if (c == '(')
                stack.push(')');
            else if (c == '{')
                stack.push('}');
            else if (c== '[') 
                stack.push(']');
            else if(stack.isEmpty() || c != stack.pop())//当不为左括号时候，说明c是右括号，
            //stack.pop弹出栈元素中存储的右括号元素，比较这两个右括号是否相等。
                return false;
        }
        if (stack.isEmpty())//判断相对情况下的第一个字符是否为’），｝，】‘这种类型的。
        //防止里面还有残余的括号
        //当stack为空时输入一个c=）时，stack内没有（与之对应，则认为false
            return true;
        return false;
    }
}

8-2 常考题型2 - 压栈匹配1(LeetCode 394题)

• 前后顺序相关联（最近遇到的东西先处理 ）
• 有特殊字符“[]...”,或字母代表特殊意义

71.

import java.util.*;
class Solution {
    public String simplifyPath(String path) {
        Stack<String> stack  = new Stack<>();
        String[] paths = path.split("/+");
        for (String s : paths) {
            if (s.equals("..")) {
                if(!stack.isEmpty()) {
                    stack.pop();
                }
            } else if (!s.equals(".") && !s.equals("")) {
                    stack.push(s);
                }
            }
            String res = "";
            while (!stack.isEmpty()) {
                res = "/" + stack.pop() + res;
            }
            if (res.length() == 0) {
                return "/";
            }
            return res;
        }
    }

8-4 常考题型3 - 表达式计算1（LeetCode 150题）

• 正常计算a + b * c
• 逆波兰表示法（后缀表达法）a b c * +

224.

/*
 * @lc app=leetcode.cn id=224 lang=java
 *
 * [224] 基本计算器
 */

// @lc code=start
class Solution {
    public int calculate(String s) {
        Stack<Integer> stack  = new Stack<>();
        int sign = 1;
        int res = 0;
        for (int i = 0; i < s.length(); i++) {
            //判断当前是否为数字
            if (Character.isDigit(s.charAt(i))) {
              	//转换成数字
                int num = s.charAt(i) - '0';
                //判断下一位是不是还是数字，case:123
                while (i + 1 < s.length() && Character.isDigit(s.charAt(i + 1))) {
                    num = num * 10 + s.charAt(i + 1) - '0';
                    i++;
                }
                res += num * sign;
            } else if (s.charAt(i) == '+') {
                sign = 1;
            } else if (s.charAt(i) == '-') {
                sign = -1;
            } else if (s.charAt(i) == '(') {
                //1 - 2可以看成 1 + (-2)
                stack.push(res);
                stack.push(sign);//sign会先Pop出来
                //恢复到初始化状态
                res = 0;
                sign = 1;
            } else if (s.charAt(i) == ')') {
                res  = res * stack.pop() + stack.pop();
            }
        }
        return res;
    }
}
// @lc code=end

常考题型4 - 迭代极值1（LeetCode 42题）

341. Flatten Nested List Iterator（压栈匹配） (08:30)

385. Mini Parser（压栈匹配） (09:15)

105. Construct Binary Tree from Preorder and Inorder Traversal (13:14)

//inorder : 有根节点的左子树在左边，右子树在右边的性质
//inorder : 当前节点下一个的位置是它的右子树
//preorder : 当前节点下一个的位置是它的左子树
//time : O(n)
//space : O(n) 递归调用
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return helper(0, 0, inorder.length - 1, preorder, inorder);
        
    }
    public TreeNode helper(int preStart, int inStart, int inEnd, int[] preorder, int[] inorder) {//不需要preorder的end
        if (preStart > preorder.length - 1 || inStart > inEnd) {
            return null;
        }
        //preorder的第一个节点就是根节点
        TreeNode root = new TreeNode(preorder[preStart]);
        //表示在Inorder中root的位置在哪
        int inIdex = 0;
        for (int i = inStart; i <= inEnd; i++) {
            if (inorder[i] == root.val) {
                inIdex = i;
            }
        }
        //prestart已经找完了，要找下一个节点，start也只能从先序遍历里面找
        root.left = helper(preStart + 1, inStart, inIdex - 1, preorder, inorder);
        //preStart + inorder中左子树的元素 + 1得到右子树的启始位置 
        root.right = helper(preStart + inIdex - inStart + 1, inIdex + 1, inEnd, preorder, inorder);
        return root;
    }
    
}

106. Construct Binary Tree from Inorder and Postorder Traversal (15:17)

class Solution {
    int pInorder;
    int pPostorder;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        pInorder = inorder.length - 1;
        pPostorder = postorder.length - 1;
        return helper(inorder, postorder, null);
    }
    public TreeNode helper(int[] inorder, int[] postorder, TreeNode end) {
        if (pPostorder < 0) {
            return null;
        }
        TreeNode root = new TreeNode(postorder[pPostorder--]);
        //代表有右孩子
        if (inorder[pInorder] != root.val) {
            root.right = helper(inorder, postorder, root);
        }
        pInorder--;//如果找到了
        if ((end == null) || (inorder[pInorder] != end.val)) {
            root.left = helper(inorder, postorder, end);
        }
        return root;
    }
}

95. Unique Binary Search Trees II（不重要） (11:41)

class Solution {
    public List<TreeNode> generateTrees(int n) {
        if (n == 0) return new ArrayList<>();
        return genTreeList(1, n);
    }

    public List<TreeNode> genTreeList(int start, int end) {
        List<TreeNode> list = new ArrayList<>();
        if (start > end) {
            list.add(null);
        }
        for (int idx = start; idx <= end; idx++) {
            List<TreeNode> leftList = genTreeList(start, idx - 1);
            List<TreeNode> rightList = genTreeList(idx + 1, end);
            for (TreeNode left : leftList) {
                for (TreeNode right : rightList) {
                    TreeNode root = new TreeNode(idx);
                    root.left = left;
                    root.right = right;
                    list.add(root);
                }
            }
        }
        return list;
    }
}

108. Convert Sorted Array to Binary Search Tree binary search（BST） (05:12)

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        if (nums == null || nums.length == 0) return null;
        return helper(nums, 0, nums.length - 1);
    }
    public TreeNode helper(int[] nums, int left, int right) {
        if (left > right) return null;
        int mid = (right - left) / 2 + left;
        TreeNode node = new TreeNode(nums[mid]);
        node.left = helper(nums, left, mid - 1);
        node.right = helper(nums, mid + 1, right);
        return node; 
    }
}

▶ 109. Convert Sorted List to Binary Search Tree binary search（BST） (04:40)

//时间复杂度是O(n) 空间复杂度O(n)
class Solution {
    //slow就是终点
    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) return null;
        return toBST(head, null);
    }
    public TreeNode toBST(ListNode head, ListNode tail) {
        if (head == tail) return null;
        ListNode slow = head;//中点
        ListNode fast = head; //走完
        while (fast != tail && fast.next != tail) {
            fast = fast.next.next;
            slow = slow.next;
        }
        TreeNode root= new TreeNode(slow.val);
        root.left = toBST(head, slow);
        root.right = toBST(slow.next ,tail);
        return root;
    }
}