day10题目：94. 二叉树的中序遍历、102. 二叉树的层序遍历、394. 字符串解码
学习计划链接：冲刺春招-精选笔面试 66 题大通关
今日知识点：树的遍历、字符串、栈，难度为简单、中等、中等
昨日题目链接：冲刺春招-精选笔面试 66 题大通关 day9
94. 二叉树的中序遍历
给定一个二叉树的根节点 root ，返回它的 中序 遍历。
示例 1：
输入： root = [1,null,2,3]
输出： [1,3,2]
示例 2：
思路
easy题，中序遍历就是 左-根-右 ，前序就是根左右，后序就是左右根。
代码
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var inorderTraversal = function(root) {
var ans = [];
var inorder = function(rt) {
if(!rt) return;
inorder(rt.left);
ans.push(rt.val);
inorder(rt.right);
}
inorder(root);
return ans;
};
102. 二叉树的层序遍历
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
示例 1：
输入： root = [3,9,20,null,null,15,7]
输出： [[3],[9,20],[15,7]]
示例 2：
输入： root = [1]
输出： [[1]]
示例 3：
思路
比昨天的题简单，每一层的结点存至q然后用nodelist暂存当前队列中所有结点（即该层的结点）后将q置空，遍历nodelist将每一个节点的孩子节点放入q
代码
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[][]}
*/
var levelOrder = function(root) {
if(!root) return [];
let ans = [];
let nowlist = [];
let q = [];
q.push(root)
while(q.length != 0) {
let nodes = q.slice(0);
q = [];
for(let v of nodes) {
nowlist.push(v.val);
if(v.left) q.push(v.left);
if(v.right) q.push(v.right);
}
ans.push(nowlist);
nowlist = [];
}
return ans;
};
394. 字符串解码
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
示例 1：
输入： s = "3[a]2[bc]"
输出： "aaabcbc"
示例 2：
输入： s = "3[a2[c]]"
输出： "accaccacc"
示例 3：
输入： s = "2[abc]3[cd]ef"
输出： "abcabccdcdcdef"
示例 4：
输入： s = "abc3[cd]xyz"
输出： "abccdcdcdxyz"
提示：
思路
遍历，若为数字则过滤出来该数字作为k，用一个栈stack存左括号，遇到右括号且栈中左括号数量不为1时出栈，当栈中只有一个左括号时，将该当前tempStr字符串递归解码后返回，重复k次后拼接至答案ans，若为其他则正常存入。
代码
/**
* @param {string} s
* @return {string}
*/
var decodeString = function(s) {
let stack = [];
let ans = '';
let len = s.length;
for(let i = 0; i < len; ++i) {
if(s[i] >= '0' && s[i] <= '9') {
let tk = s[i++];
while(i < len && s[i] >= '0' && s[i] <= '9')
tk += s[i++];
let k = parseInt(tk);
let tempStr = '';
stack.push(s[i++]); // 放入'['
while(i < len && (s[i] != ']' || stack.length != 1)) { // 若s[i] == ']' 并且 stack中只有一个时结束
if(s[i] == '[') {
stack.push(s[i]);
} else if(s[i] == ']')
stack.pop();
tempStr += s[i];
++i;
}
stack.pop();
let decode = decodeString(tempStr); // 核心
ans += `${decode.repeat(k)}`;
} else ans += s[i];
}
return ans;
};
