leetcode 7.06-7.12

2020-07-12

面试题08.09 括号
94 二叉树的中序遍历

面试题08.09. 括号

括号。设计一种算法，打印n对括号的所有合法的（例如，开闭一一对应）组合。

说明：解集不能包含重复的子集。

例如，给出 n = 3，生成结果为：

[
“((()))”,
“(()())”,
“(())()”,
“()(())”,
“()()()”
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/bracket-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：递归，在子串的基础上通过添加左右括号生成新串。left表示左括号剩余的量，right表示右括号剩余的量。字符串一定以左括号开始。以左括号为根，生成的字符串可以用二叉树表示，其中一些分支是不符合要求的，比如right < left的情况。

AC代码：

class Solution {
private:
    vector<string> ret;

    void parenthesis(int left, int right, string s) {
        if (left == 0 && left == right) {
            ret.push_back(s);
        }

        if (left > 0)
            parenthesis(left - 1, right, s + "(");
        if (right > left) 
            parenthesis(left, right - 1, s + ")");
    }

public:
    vector<string> generateParenthesis(int n) {
        parenthesis(n, n, "");
        return ret;
    }
};

94. 二叉树的中序遍历

思路：与前序遍历类似，用栈保存节点，每次循环先把所有左节点加入栈，然后开始pop访问，并把右节点加入栈。

AC代码：

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> ret;
        if(!root) return ret;
        auto p = root;
        do {
            while(p){
                st.push(p);
                p = p->left;
            }
            p = st.top();
            st.pop();
            ret.push_back(p->val);
            p = p->right;
        } while(!(p == NULL && st.empty()));
        return ret;
    }
};