day3 #栈 leetcode热题100

1.题目描述

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。

左括号必须以正确的顺序闭合。

#python

class Solution:

    def isValid(self, s: str) -> bool:

        if len(s) % 2 == 1:

            return False

        #思考奇数肯定不对

        pairs = {

            ")": "(",

            "]": "[",

            "}": "{",

        }

        stack = list()

        for ch in s:

            if ch in pairs:

                if not stack or stack[-1] != pairs[ch]:

                    return False

                stack.pop()

            else:

                stack.append(ch)

        return not stack

2.题目描述

给定一个二叉树的根节点 root ，返回它的 中序遍历。

这道题目按照要求遍历数就是  左 根  右的顺序

解法一：递归

class Solution(object):

   def inorderTraversal(self, root):

        res = []

        def dfs(root):

            if not root:

                return

            # 按照 左-打印-右的方式遍历    

            dfs(root.left)

            res.append(root.val)

            dfs(root.right)

        dfs(root)

        return res