头像

诶嘿-




离线:1天前


最近来访(0)


诶嘿-
2天前
class Solution {
public:
    TreeNode* pre = NULL;
    TreeNode* convert(TreeNode* root) {
        if(!root) return NULL;
        dfs(root);
        while(root->left) root = root->left;
        return root;

    }
    void dfs(TreeNode* root){
        if(!root) return;
        auto r = root->right;
        dfs(root->left);
        if(pre) pre->right = root;
        root->left = pre;
        pre = root;
        dfs(r);
;


    }
};



诶嘿-
3天前

题目描述

哈希表方法

样例

func copyRandomList(head *ListNode) *ListNode {
    r := make(map[*ListNode]*ListNode)
    t := &ListNode{Val: 0, Next: nil, Random: nil}
    s := head
    ans := t
    for head != nil {
        t.Next = &ListNode{Val: head.Val, Next: nil, Random: nil}
        t = t.Next
        r[head] = t
        head = head.Next
    }
    for s != nil {
        if s.Random != nil {
            r[s].Random = r[s.Random]

        }
        s = s.Next
    }
    return ans.Next
}



诶嘿-
3天前
class Solution {
public:
    ListNode *copyRandomList(ListNode *head) {
        unordered_map<ListNode*, ListNode*> f;
        ListNode* p = new ListNode(0);
        ListNode* h = p;
        ListNode* o = head;
        while(head){
            p->next = new ListNode(head->val);
            p = p->next;
            f[head] = p;
            head = head->next;
        }
        while(o){
            if(o->random != NULL) f[o]->random = f[o->random];
            o = o->next;
        }
        return h->next;
    }
};




诶嘿-
4天前

题目描述

Go实现,思路和C++一样,然而go的数组需要深拷贝

样例

var res [][]int

func findPath(root *TreeNode, sum int) [][]int {
    dfs(root, sum, []int{})
    return res
}

func dfs(root *TreeNode, sum int, path []int) {
    if root == nil {
        return
    }
    sum -= root.Val
    path = append(path, root.Val)
    if sum == 0 && root.Left == nil && root.Right == nil {

        newPath := make([]int, len(path))
        copy(newPath, path)
        res = append(res, newPath)
    }
    dfs(root.Left, sum, path)
    dfs(root.Right, sum, path)

}



诶嘿-
4天前
var res [][]int

func findPath(root *TreeNode, sum int) [][]int {
    dfs(root, sum, []int{})
    return res
}

func dfs(root *TreeNode, sum int, path []int) {
    if root == nil {
        return
    }
    sum -= root.Val
    path = append(path, root.Val)
    if sum == 0 && root.Left == nil && root.Right == nil {

        newPath := make([]int, len(path))
        copy(newPath, path)
        res = append(res, newPath)
    }
    dfs(root.Left, sum, path)
    dfs(root.Right, sum, path)

}



诶嘿-
4天前

题目描述

二叉搜索树的后序遍历序列, GO实现

Go 代码

var seq []int

func dfs(l int, r int) bool {
    if l >= r {
        return true
    }
    var (
        root = seq[r]
        k    = l
    )

    for seq[k] < root && k < r {
        k += 1
    }
    for i := k; i < r; i += 1 {
        if seq[i] < root {
            return false
        }
    }
    return dfs(l, k-1) && dfs(k, r-1)

}
func verifySequenceOfBST(sequence []int) bool {
    seq = sequence
    return dfs(0, len(seq)-1)
}



诶嘿-
4天前
class Solution {
public:
    vector<int> seq;

    bool verifySequenceOfBST(vector<int> sequence) {
        int n = sequence.size() - 1;
        if(n==-1) return true;
        int root = sequence[n];
        seq = sequence;
        return dfs(0, n);
    }

    bool dfs(int l, int r){
        if(l >= r) return true;
        int root = seq[r];
        int k = l;
        while(seq[k] < root && k < r) k++;
        for(int i = k; i < r; i++){
            if(seq[i] < root) return false;
        }
        return dfs(l, k - 1) && dfs(k, r - 1);    
    }

};



诶嘿-
5天前
/**
 * 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<vector<int>> printFromTopToBottom(TreeNode* root) {
        vector<vector<int>> res;
        queue<TreeNode*> r;
        if(root) r.push(root);
        bool c = true;
        while(r.size()){
            int len = r.size();
            vector<int> row;

            while(len--){
                auto a = r.front();
                r.pop();
                row.push_back(a->val);
                if(a->left) r.push(a->left);
                if(a->right) r.push(a->right);
            }
            if(c) res.push_back(row);
            else{
                reverse(row.begin(),row.end());
                res.push_back(row);
            }
            c = !c;
        }
        return res;
    }
};




诶嘿-
5天前
class Solution {
public:
    vector<vector<int>> printFromTopToBottom(TreeNode* root) {

        vector<vector<int>> res;
        queue<TreeNode*> r;
        if(root) r.push(root);
        while(r.size()){
            int len = r.size();
            vector<int> row;

            while(len--){
                auto a = r.front();
                r.pop();
                row.push_back(a->val);
                if(a->left) r.push(a->left);
                if(a->right) r.push(a->right);
            }
            if(row.size()) res.push_back(row);
        }
        return res;
    }
};



诶嘿-
5天前
class Solution {
public:
    vector<int> printFromTopToBottom(TreeNode* root) {
        if(!root) return vector<int>();
        queue<TreeNode*> r;
        vector<int> res ;
        r.push(root);
        while(r.size()){
            auto a = r.front();
            r.pop();
            res.push_back(a->val);
            if(a->left) r.push(a->left);
            if(a->right) r.push(a->right);
        }
        return res;

    }
};