• 10.16
  • ①有效的括号
  • ②二叉树的中序遍历

10.16

①有效的括号

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

示例 1：

输入：s = "()"
输出：true
示例 2：

输入：s = "()[]{}"
输出：true
示例 3：

输入：s = "(]"
输出：false
示例 4：

输入：s = "([)]"
输出：false
示例 5：

输入：s = "{[]}"
输出：true

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-parentheses

代码:

const leftToRight = {
	"{"："}",
	"[":"]",
	"(":")"
}
var isValid = function(s){
	//结合题意,空字符串无条件判断为true
	if(!s)return true
	//初始化数组stack
	let stack = []
	//缓存字符串长度
	const len = s.length
	//遍历字符串
	for(let i=0;i<len;i++){
		//缓存单个字符
		const ch = s[i]
		//判断是否是左括号
		if(ch==="("||ch==="["||ch==="{"){
			stack.push(leftToRight[ch])
		}else{
			//若栈不为空，且栈顶的左括号没有和当前字符匹配上，那么判为无效
			if(!stack.length||stack.pop()!==ch){
				return false
			}
		}
	}
	//若所有的括号都能配对成功，那么最后栈应该是空的
	return !stack.length
}

②二叉树的中序遍历

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

示例 1：

输入：root = [1,null,2,3]
输出：[1,3,2]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-inorder-traversal

代码：
使用递归

var inorderTraversal = function(root,res=[]){
	if(!root){
		return
	}
	inorderTraversal(root.left,res)
	res.push(root.val)
	inorderTraversal(root.right,res)
	return res
}