头像

st


访客:12341

离线:6个月前



st
2019-03-02 23:29

题目描述

给定一个非空字符串ss和一个非空词典wordDictwordDict,判断ss是否能被分割成一个或多个单词分隔的序列。

注意,词典中的词可以用多次,词典中没有重复的单词。

样例

Example 1:

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释:  "leetcode" 可以被切割成 "leet code"

Example 2:

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: "applepenapple" 可以被切割成 "apple pen apple"

Example 3:

输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false


算法1

(brute force with recursion) $O(n^n)$

check every possible prefix of that string in the dictionary of words, if it is found in the dictionary, then the recursive function is called for the remaining portion of that string.

base case: if in some function call it is found that the complete string is in dictionary, then it will return true.

时间复杂度分析:worst case sssssss, every prefix is present in the dictionary of words, then the recursion tree can grow upto $O(n^n)$

C++ 代码

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        if(wordDict.size()==0) return false;
        set<string> _wordDict;
        for(auto &x: wordDict){
            _wordDict.insert(x);
        }
        return _wordBreak(s, _wordDict, 0);
    }
    bool _wordBreak(string s, set<string> _wordDict, int start){
        if(start == s.length())
            return true;
        for(int j = 0; start + j <= s.length(); j++){
            if(_wordDict.count(s.substr(start, j)) && _wordBreak(s, _wordDict, start + j)){
                return true;
            }
        }
        return false;
    }
};
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        return _wordBreak(s, wordDict, 0);
    }
    bool _wordBreak(string s, vector<string> wordDict, int start){
        if(start == s.length())
            return true;
        for(auto w: wordDict){
            int end = start + w.size()-1;
            if(end < s.length() && s.substr(start, w.size()) == w){
                if(start + w.size() == s.length())
                    return true;
                else if(_wordBreak(s, wordDict, end+1))
                    return true;
            }
        }       
        return false;
    }
};


算法2

(Recursion with memoization) $O(n^2)$

use a set memo to store the false subproblems so that when the recursive function is called with a case we have eevaluated before, we can directly return false without redundant calculation.

the prefix must be true then the recursive function is called. there is no need to store the end index returning true.

时间复杂度分析:$O(n^2)$

C++ 代码

class Solution {
public:
    vector<string> _wordDict;
    set<int> vis;
    bool wordBreak(string s, vector<string>& wordDict) {
        _wordDict = wordDict;
        return _wordBreak(s, 0);
    }
    bool _wordBreak(string s, int start){
        for(auto &w: _wordDict){
            int end = start + w.length()-1;
            if(end < s.length() && s.substr(start, w.size()) == w){
                if(start + w.size() == s.size())
                    return true;
                else if(vis.find(end) != vis.end())
                    return false;
                else if(_wordBreak(s, end+1))
                    return true;
                else vis.insert(end);
            }
        }
        return false;
    }
};

算法3

(bfs) $O(n^2)$

Think the string as a tree, where each node is a prefix/word. Two nodes are connected only if the two words are included in the dict.

The traverse start from the first character of the string and find every possible substring starting with that character. The end index of each word would be pushed in the queue.

If we are able to obtain the last element of the given string as a node (leaf) of the tree, this implies that the given string can be partitioned into substrings which are all a part of the given dictionary.

Use a memo to store some results otherwise would TLE.

时间复杂度分析:$O(n^2)$

C++ 代码

// bfs
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        queue<int> prefixQ;
        set<int> vis; //memo
        prefixQ.push(0);
        while(!prefixQ.empty()){
            int start = prefixQ.front();
            prefixQ.pop();
            if(vis.find(start) == vis.end()){
                for(auto w: wordDict){
                        int end = start + w.size()-1;
                        if(end < s.length() && s.substr(start, w.size()) == w){
                            if(start + w.size() == s.size())
                                return true;
                            else {
                                prefixQ.push(end+1);
                            }                        
                        }   
                }
                vis.insert(start);
            }
        }
        return false;
    }   
};

算法4

(dp) $O(n^2)$

dp 隔板
注意substr(j, i-j)

时间复杂度分析:$O(n^2)$

C++ 代码


// dp
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        set<string> _wordDict(wordDict.begin(), wordDict.end());
        vector<bool> dp(s.size()+1, false);
        dp[0] = true;
        for(int i = 0; i <= s.size(); i++){
            for(int j = i; j >= 0; j--){
                if(dp[j]){
                    string word = s.substr(j,i-j);
                    if(_wordDict.find(word)!= _wordDict.end()){
                        dp[i]=true;
                        break; 
                    }
                }

            }
        }
        return dp[s.size()];
    }
};




st
2019-03-01 23:32

题目描述

给定一个单链表,链表中的每个节点包含一个额外的指针,随机指向链表中的其它节点或者指向 null。
请复制整个链表,并返回新链表的头结点。


算法1

(recursive) $O(n^2)$

intuitively, 这个每个node有多个指针的链表很像一个图,所以最先想到的是图的遍历。用dfs recursively traverse这个图,clone每一个node。只不过->child这里是->next和->random。

时间复杂度分析:blablabla

C++ 代码

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node() {}

    Node(int _val, Node* _next, Node* _random) {
        val = _val;
        next = _next;
        random = _random;
    }
};
*/
class Solution {
public:
    unordered_map<Node*, Node*> visHash; //assigned outside otherwise stackoverflow
    Node* copyRandomList(Node* head) {
        if(!head) 
            return NULL;
        if(visHash.count(head))
            return visHash[head];
        Node* root = new Node(head->val, NULL, NULL);
        visHash[head] = root;
        root->next = copyRandomList(head->next);
        root->random = copyRandomList(head->random);
        return root;
    }
};

算法2

(iterative) $O(n)$

link the nodes inside the hash table

好像这题的def Node变了。写了个最新版本。

时间复杂度分析:遍历一遍,$O(n)$

C++ 代码

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node() {}

    Node(int _val, Node* _next, Node* _random) {
        val = _val;
        next = _next;
        random = _random;
    }
};
*/
class Solution {
public:
    Node* copyRandomList(Node* head) {
        unordered_map<Node*, Node*> hash;
        if(!head) 
            return NULL;
        Node* root = new Node(head->val, NULL, NULL);
        hash[head] = root;
        while(head->next){
            if(!hash.count(head->next)){
                hash[head->next] = new Node(head->next->val, NULL, NULL);
            }
            hash[head]->next = hash[head->next];
            if(head->random && !hash.count(head->random)){
                hash[head->random] = new Node(head->random->val, NULL, NULL);
            }
            hash[head]->random = hash[head->random];
            head = head->next;
        }
        if(head->random && !hash.count(head->random)){
            hash[head->random] = new Node(head->random->val, NULL, NULL);
        }
        hash[head]->random = hash[head->random];

        return root;

    }
};

算法3

(iterative with O(1) space) $O(n)$

不需要额外map存copy,in place修改input linked list,然后再restore。

1.copy each node. insert the copy node next to the corresponding original one.
2.traverse the list, copy the random ptr
3.restore the original list and return the new one

时间复杂度分析:$O(n)$

C++ 代码

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node() {}

    Node(int _val, Node* _next, Node* _random) {
        val = _val;
        next = _next;
        random = _random;
    }
};
*/
class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(!head)
            return head;
        Node* l1, *l2, *root;
        for(l1 = head; l1 ; l1 = l1->next->next){
            l2 = new Node(l1->val, NULL, NULL);
            l2->next = l1->next;
            l1->next = l2;
        }
        root = head->next;
        for(l1 = head; l1; l1 = l1->next->next){
            if(l1->random){
                l1->next->random = l1->random->next;
            }
        }
        for(l1 = head; l1;l1 = l1->next){
            l2 = l1->next;
            l1->next = l2->next;
            if(l2->next)
                l2->next = l2->next->next;
        }
        return root;
    }
};



st
2019-03-01 07:22

题目描述

类似于Two Sum,给定一个整型数组,要求返回所有不重复的三元组,且每个三元组的和等于0。

样例

给定数组 nums = [-1, 0, 1, 2, -1, -4],返回 [ [-1, 0, 1], [-1, -1, 2] ]。

算法0

(暴力枚举,排序去重) $O(n^3 logn)$

时间复杂度分析:$O(n^3 logn)$

C++ 代码

blablabla

算法1

(两重枚举) $O(n^2)$

为了防止放进result有相同答案,每次得到一个答案之后,跳过所有nums[i]的duplicate,并删除hashset中的i。
这样做保证了对每一个st,有且最多只有一个i与之匹配,因为已经sort过,故不会有重复答案出现。

时间复杂度分析: $O(n^2)$

C++ 代码

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        unordered_set<int> hash;
        sort(nums.begin(), nums.end());
        for (int st = 0; st < nums.size(); st++) {
            int n = nums.size();
            while (st > 0 && st < n && nums[st] == nums[st - 1])
                st++;
            hash.clear();
            for (int i = st + 1; i < nums.size(); i++) {
                unordered_set<int>::const_iterator got = hash.find(- nums[st] - nums[i]);
                if (got == hash.end())
                    hash.insert(nums[i]);
                else {
                    res.push_back({nums[st], nums[i], - nums[st] - nums[i]});
                    hash.erase(nums[i]);
                    while(i > 0 && i < n-1 && nums[i+1] == nums[i]) i++;
                }
            }
        }
        return res;
    }
};


算法2

(两重枚举,集合判重) $O(n^2)$

注意循环的时候数组越界

时间复杂度分析: $O(n^2)$

C++ 代码

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        unordered_set<int> hash, vis;
        sort(nums.begin(), nums.end());

        for (int st = 0; st < nums.size(); st++) {
            while (st > 0 && st < nums.size() && nums[st] == nums[st - 1])
                st++;
            hash.clear();
            vis.clear();
            for (int i = st + 1; i < nums.size(); i++) {
                unordered_set<int>::const_iterator got = hash.find(- nums[st] - nums[i]);
                if (got == hash.end())
                    hash.insert(nums[i]);
                else {
                    res.push_back({nums[st], nums[i], - nums[st] - nums[i]});
                    vis.insert(- nums[st] - nums[i]);
                }
                if (vis.find(- nums[st] - nums[i]) != vis.end())
                    hash.erase(- nums[st] - nums[i]);
            }
        }
        return res;
    }
};


算法3

(双指针) $O(n^2)$

注意循环的时候数组越界。
对每一个st,双指针头尾扫。

时间复杂度分析: $O(n^2)$

C++ 代码

class Solution {
public:
   vector<vector<int>> threeSum(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    vector<vector<int>> res;
    for (int i=0; i<nums.size(); i++) {
        if ((i>0) && (i<nums.size()) && (nums[i]==nums[i-1]))
            continue;
        int l = i+1, r = nums.size()-1;
        while (l<r) {
            int s = nums[i]+nums[l]+nums[r];
            if (s>0) r--;
            else if (s<0) l++;
            else {
                res.push_back(vector<int> {nums[i], nums[l], nums[r]});
                while (l<r && nums[l]==nums[l+1]) l++;
                while (l<r && nums[r]==nums[r-1]) r--;
                l++; r--;
            }
        }
    }
    return res;
}
};





st
2019-02-28 21:16

题目描述

给定一个字符串,返回它的最长回文子串。如果存在多个答案,返回任意一个即可。字符串长度 ≤≤ 1000。

样例

输入:"babad"
输出:"bab"
注意:"aba" 也是一个合法的答案.

算法0

(intuitive way) $O(n^2)$

最容易想到的方法是reverse然后找前后两条string的LCS. 但这是不对的。如果原序列中分别包含两条不邻接的互为reverse的substring,就会被算入LCS,但其实这并不是palindromic的。所以还需要检查一下LCS的index是否一致。

时间复杂度分析:与寻找最长公共子序列的复杂度一致。$O(n^2)$

C++ 代码

blablabla

算法1

(暴力枚举) $O(n^3)$

枚举所有substring 判断是否palindrome。

时间复杂度分析:substring(including a char itself)一共有C(n,2)+n。判断是否palindrome要O(n),一共$O(n^3)$

C++ 代码

blablabla

算法2

(dp) $O(n^2)$

p(i, j) reperesent whether the substring between i and j (inclusive) is a palindrome.

transition function: p(i, j) = p(i+1, j-1) && (s[i] == s[j])
base case: p(i, i) = true; p(i, i+1) = (s[i] == s[i+1]);

时间复杂度分析:时间$O(n^2)$ 空间$O(n^2)$(two dimentional array p)

C++ 代码


class Solution {
public:
    string maxStr = "";
    string longestPalindrome(string s) {
        if(!s.length())
            return maxStr;
        if(s.length()==1) 
            return s;
        int n = s.length();
        bool p[n][n] = {false};
        for(int i = 0; i < n-1; i++){
            p[i][i] = true;
            p[i][i+1] = (s[i] == s[i+1]);
        }
        p[n-1][n-1] = true;
        p[n-2][n-1] = (s[n-2] == s[n-1]);
        for(int j = 2; j < n; j++){
            for(int i = j-2; i >= 0; i--){
                p[i][j] = (p[i+1][j-1] && s[i] == s[j]);
            }
        }
        for(int i = 0; i < n; i++){
            for(int j = i; j < n; j++){
                if(p[i][j] && (j-i+1 > maxStr.length())){
                    printf("pij = %d %d %d \n", i, j, p[i][j]);
                    maxStr = s.substr(i, j-i+1);
                }
            }
        }
        return maxStr;
    }
};

算法3

(yxc的方法 枚举center and expand from the center) $O(n^2)$

时间复杂度分析:时间$O(n^2)$ 一共有2n-1个center。每个center expand O(n)。

C++ 代码

class Solution {
public:
    string maxStr = "";
    string longestPalindrome(string s) {
        if(!s.length() || s.length()==1) return s;
        for(int i = 0; i < s.size(); i++){
            for(int j = 0; i-j>=0 && i+j<s.length(); j++){
                if(s[i-j] == s[i+j]){
                    //printf("i-j= %d, i+j= %d\n", i-j, i+j);
                    //printf("i = %d, j = %d\n", i, j);
                    if(j*2+1 > maxStr.length())
                        maxStr = s.substr(i-j, j*2+1);
                }
                else break;

            }
            for(int j = 0; i-j>=0 && i+1+j<s.length(); j++){
                if(s[i] == s[i+1] && s[i-j] == s[i+1+j]){
                    if (j*2+2 > maxStr.length())
                        maxStr = s.substr(i-j, j*2+2);
                }
                else break;

            }
        }
        return maxStr;
    }
};

算法4

Manacher’s Algorithm $O(n)$

并没有看太懂……要是yxc大佬有空求写一下通俗讲解版本。

时间复杂度分析: $O(n)$

C++ 代码

class Solution {
public:
    string longestPalindrome(string s) 
    {
        string T;// Transform S to T
        for(int i=0;i<s.size();i++)
            T+="#"+s.substr(i,1);
        T.push_back('#');

        vector<int> P(T.size(),0); // Array to record longest palindrome
        int center=0,boundary=0,maxLen=0,resCenter=0;
        for(int i=1;i<T.size()-1;i++) {
            int iMirror=2*center-i; // calc mirror i = center-(i-center)
            P[i]=(boundary>i)?min(boundary-i,P[iMirror]):0; // shortcut
            while(i-1-P[i]>=0&&i+1+P[i]<=T.size()-1&&T[i+1+P[i]] == T[i-1-P[i]]) // Attempt to expand palindrome centered at i
                P[i]++;
            if(i+P[i]>boundary) { // update center and boundary
                center = i;
                boundary = i+P[i];
            }
            if(P[i]>maxLen) { // update result
                maxLen = P[i];
                resCenter = i;
            }    
        }
        return s.substr((resCenter - maxLen)/2, maxLen);
    }
};



st
2019-02-28 08:59

题目描述

给定一个字符串,请找出最长的不包含重复字符的子串。
请注意子串和子序列的区别:

子串一定是连续的一段
子序列不一定是连续的一段,但下标要求是递增的

样例

给定 "abcabcbb",答案是"abc",长度是3.
给定 "bbbbb",答案是"b",长度是1.
给定 "pwwkew",答案是"wke",长度是3.


算法1

(暴力枚举) $O(n^3)$

两重循环枚举所有substring。对于每个substring再用一重循环判断是否unique。总时间复杂度是 $O(n^3)$ 。

时间复杂度分析: $O(n^3)$

C++ 代码

// brute force 
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int maxLen = 0;
        if(!s.size())
            return maxLen;
        for(int i = 0; i < s.size(); i++){
            for(int j = 0; j < s.size(); j++){
                if(isUniq(s, i, j))
                    maxLen = max(maxLen, j-i+1);
            }
        }
        return maxLen;
    }
    bool isUniq(string s, int start, int end){
        set<char> uniqSet;
        for(int i = start; i <= end; i++){
            if(uniqSet.count(s[i]))
                return false;
            uniqSet.insert(s[i]);
        }
        return true;
    }
};

算法2

(slide window with set or hashmap) $O(2n)$

yxc的方法好像属于这一类。hashmap或set里保存该双指针中间的substring的char frequency。右端指针每前进一位要到hashmap/set里判断是否出现过。如果出现,左端指针前进一位并更新hashmap/set,直到右端指针指向的char被删掉为止,然后更新maxLen。

用set还是hashmap个人觉得完全没区别。

时间复杂度分析:最坏情况每个char被左右指针分别访问一次(全重复序列)。遍历了2n个状态,所以复杂度$O(2n)$。(为了和下面的区分)

C++ 代码


// slide window with set
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int maxLen = 0;
        set<char> uniqSet;
        if(!s.length()) 
            return maxLen;
        int n = s.length();
        int i = 0, j = 0;
        while(i<n && j<n){
            if(!uniqSet.count(s[j])){
                uniqSet.insert(s[j]);
                maxLen = max(maxLen, j-i+1);
                j++;
            }
            else{

                uniqSet.erase(s[i]);
                i++;

            }
        }
        return maxLen;
    }
};

// slide window with hashmap
class Solution {
public:
    int ans = 0;
    int lengthOfLongestSubstring(string s) {
        unordered_map<char ,int> hash;
        if(s == "") return ans;
        for(int i = 0, j = 0; j < s.size(); j++){
            if(++hash[s[j]] > 1){
                while(i < j){
                    hash[s[i]]--;
                    i++;
                    if(hash[s[j]] == 1){
                        break;
                    } 
                }
            }
        ans = max(ans, j-i+1);
        }
        return ans;
    }
};


算法3

(slide window optimized with hashmap) $O(n)$

减少了平均访问到的状态的个数。

hashmap key是char value是最后一次访问到该char的index。右端指针每前进一位要到hashmap里判断是否出现过。如果出现,左端指针前进到该重复char的最后一次出现的index的后一位。相当于直接跳过了一段与没有包含该重复char的序列。更新hashmap,然后更新maxLen。

时间复杂度分析: 稳定$O(n)$。

C++ 代码


// slide window optimized with hashmap
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.length();
        int maxLen = 0;
        unordered_map<char, int> charToIdx;
        for(int i = 0, j = 0; j < n; j++){
            if(charToIdx.count(s[j]))
                i = max(i, charToIdx[s[j]]);
            maxLen = max(maxLen, j-i+1);
            charToIdx[s[j]] = j+1;
        }
        return maxLen;
    }
};

算法4

(slide window fastest) $O(n)$

原理同前。更快了而已。

时间复杂度分析: $O(n)$。

C++ 代码


// slide window quick
class Solution{
public:
int lengthOfLongestSubstring(string s) {
        vector<int> charToIdx(256, -1);
        int maxLen = 0;
        for (int i = -1, j = 0; j != s.length(); j++) {
            if (charToIdx[s[j]] > i)
                i = charToIdx[s[j]];
            charToIdx[s[j]] = j;
            maxLen = max(maxLen, j - i);
        }
        return maxLen;
    }
};



//分析的不对的地方求指正。




st
2019-01-13 07:18
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
class Solution {
public:
    bool isNumber(string s) {
        int i = 0;
        while(i<s.size() && s[i] == ' ') i++;
        int j = s.size()-1;
        while(j>=0 && s[j] == ' ') j--;
        if(i>j) return false;
        s = s.substr(i,j-i+1);
        if(s[0] == '-' || s[0] == '+') s = s.substr(1);
        if(s.empty() || s[0] == '.' && s.size() == 1) return false;
        int dot = 0, e = 0;
        for(int i = 0; i < s.size(); i++){
            if(s[i] >= '0' && s[i] <= '9');
            else if(s[i] == '.'){
                dot++;
                if(e || dot>1) return false;
            }
            else if(s[i] == 'e' || s[i] == 'E'){
                e++;
                if(i == s.size()-1 || !i || e>1 || i==1 && s[0]=='.') return false;
                if(s[i+1] == '+' || s[i+1] == '-'){
                    if(i+1 == s.size()-1) return false;
                    i++;
                }
            }
            else return false;
        }
        return true;
    }
};



st
2019-01-13 06:56
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
class Solution {
public:
    bool isMatch(string s, string p) {
        int n = s.length(), m = p.length();
        vector<vector<int>> f(n+1, vector<int>(m+1, 0));
        s = " " + s, p = " " + p;
        f[0][0] = 1;
        for(int i = 0; i <= n; i++){
            for(int j = 1; j <= m; j++){
                if(i > 0 && ((s[i] == p[j] || p[j] == '.') && f[i-1][j-1])) f[i][j] = 1;
                if(p[j] == '*' && f[i][j-2]) f[i][j] = 1;
                if(i>0 && p[j] == '*' && (s[i] == p[j-1] || p[j-1] == '.') && f[i-1][j-2]) f[i][j] = 1;
                if(i>0 && p[j] == '*' && (s[i] == p[j-1] || p[j-1] == '.') && f[i-1][j]) f[i][j] = 1;

            }
        }
        return f[n][m];
    }
};



st
2019-01-13 05:01
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
class Solution {
public:
    vector<int> get_val(vector<TreeNode*> level)
    {
        vector<int> res;
        for (auto &u : level)
            res.push_back(u->val);
        return res;
    }
    vector<vector<int>> printFromTopToBottom(TreeNode* root) {
        vector<vector<int>>res;
        if (!root) return res;
        vector<TreeNode*>level;
        level.push_back(root);
        res.push_back(get_val(level));
        bool zigzag = true;
        while (true)
        {
            vector<TreeNode*> newLevel;
            for (auto &u : level)
            {
                if (u->left) newLevel.push_back(u->left);
                if (u->right) newLevel.push_back(u->right);
            }
            if (newLevel.size())
            {
                vector<int>temp = get_val(newLevel);
                if (zigzag)
                    reverse(temp.begin(), temp.end());
                res.push_back(temp);
                level = newLevel;
            }
            else break;
            zigzag = !zigzag;
        }
        return res;
    }
};



st
2019-01-13 04:26
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> get_val(queue<TreeNode*> q){
        vector<int> ans;
        while(!q.empty()){ 
            TreeNode* x = q.front();
            ans.push_back(x->val);
            q.pop();
        }
        return ans;
    }
    vector<vector<int>> printFromTopToBottom(TreeNode* root) {
        vector<vector<int>> ans;
        if(!root) return ans;
        queue<TreeNode*> q;
        q.push(root);
        ans.push_back(get_val(q));
        while(1){
        queue<TreeNode*> new_q;
        while(!q.empty()){
            TreeNode* t = q.front();
            q.pop();
            if(t->left) new_q.push(t->left);
            if(t->right) new_q.push(t->right);
        }
        if(!new_q.empty()) {
            ans.push_back(get_val(new_q));
            q = new_q;
        }
        else break;
        }
        return ans;
    }
};



st
2019-01-13 04:10
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> printFromTopToBottom(TreeNode* root) {
        vector<int> ans;
        if(!root) return ans;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()){
            TreeNode* t = q.front();
            q.pop();
            if(t->left) q.push(t->left);
            if(t->right) q.push(t->right);
            ans.push_back(t->val);
        }
        return ans;
    }
};