BFS, DFS, In-order traversal

[sync-by-unito[bot]]

FB Questions: //301. Remove Invalid Parentheses [Hard] //199. Binary Tree Right Side View [Med] //BFS with level order traversal //124. Binary Tree Maximum Path Sum [Hard] //297. Serialize and Deserialize Binary Tree [Hard]

Classic: //98. Validate Binary Search Tree [Med] //in-order traversal //230. Kth Smallest Element in a BST [Med] //104. Maximum Depth of Binary Tree [Easy]

┆Issue is synchronized with this Trello card by Unito

[sync-by-unito[bot]]

➤ Nelson 3513 commented:

//230. Kth Smallest Element in a BST [Med]

class Solution_q230 { public: //In-order traversal (BST's in-order traversal is a sorted list) int kthSmallest(TreeNode* root, int& k) { if (!root) return -1;

    //left
    int res = kthSmallest(root->left, k);
    if (!k) return res;

    //current
    if (!--k) return root->val;

    //right
    return kthSmallest(root->right, k);
}

};

[sync-by-unito[bot]]

➤ Nelson 3513 commented:

//98. Validate Binary Search Tree [Med]

bool isValidBST(TreeNode node, TreeNode& prev) { if (!node) return true; //Because in-order traversal (left, root, right) for a BST will be a sorted list, //We can simply traverse it this way, make sure current val is bigger than pre val.

//left
if (!isValidBST(node->left, prev)) return false;
//current
if (prev && node->val <= prev->val) return false;
prev = node;
//right
return isValidBST(node->right, prev);

} bool isValidBST(TreeNode root) { TreeNode prev = nullptr; return isValidBST(root, prev); }

[sync-by-unito[bot]]

➤ Nelson 3513 commented:

//104. Maximum Depth of Binary Tree [Easy]

class Solution_q104 { public: int maxDepth(TreeNode* root) { if (!root) return 0; return std::max(maxDepth(root->left), maxDepth(root->right)) + 1; } };

[sync-by-unito[bot]]

➤ Nelson 3513 commented:

//301. Remove Invalid Parentheses [Hard] // Add '(' , ')' or not to add them, decision making and string generation

class Solution { public: void dfs(string &s, size_t idx, int unpair, int l, int r, string path, unordered_set& res) { if(r < 0 || r < 0 || unpair < 0) // Eliminate unnecessary generations. return;

    if (idx == s.size()){
        if(l == 0 && r == 0 && unpair == 0) res.insert(path);
        return;
    } else {
        if (s[idx] == '('){
            //2 choices: one is is to add '(',')'; the other is not to add them
            dfs(s, idx+1, unpair+1, l, r, path+s[idx], res);
            dfs(s, idx+1, unpair, l-1, r, path, res);
        }else if (s[idx] == ')'){
            dfs(s, idx+1, unpair-1, l, r, path+s[idx], res);
            dfs(s, idx+1, unpair, l, r-1, path, res);
        }else{ //for characters not '(' nor ')'
            dfs(s, idx+1, unpair, l, r, path+s[idx], res); 
        }
    }
    return;
}

vector<string> removeInvalidParentheses(string s) {
    // Step 0. remove prefixing ')' and postfixing '(';
    /*size_t p1 = s.find_first_not_of(')');
    size_t p2 = s.find_last_not_of('(');
    cout << "P1:" << p1 << ", P2:" << p2 << endl;
    if(p1 > s.size() || p2 > s.size()) return {""};
    s = s.substr(p1, p2-p1+1); cout << s; //s = s.substr(p1, (s.size()-p1)-(s.size()-p2)+1 );*/

    // Step 1. count unclosing '(' and ')', so we know how many and what to remove.
    int l = 0; // l: number of '(' to be removed 
    int r = 0; // r: number of ')' to be removed
    for(size_t i=0; i < s.size(); i++){
        if(s[i] == '(') ++l;
        else if(s[i] == ')' && l > 0) --l;
        else if(s[i] == ')' && l == 0) ++r;
    }

    // Step 2. recursively generate parentheses,
    // two choices: remove/not add '(' / ')', or append the characters.
    unordered_set<string> set;
    dfs(s, 0, 0, l, r, "", set);
    return vector<string>(set.cbegin(), set.cend());
}

};

[sync-by-unito[bot]]

➤ Nelson 3513 commented:

//199. Binary Tree Right Side View [Med] //BFS with two queue to get level base traversal.

public: vector rightSideView(TreeNode root) { if(!root) return {}; vector res; queue<TreeNode> curlv, nextlv; nextlv.push(root);

    while (!nextlv.empty()) {
        // Step 1. swap all items in nextlv into curlv, and then we process all items in curlv.
        curlv.swap(nextlv);

        // Step 2. add child items into nextlv, the last one will be the right most item
        while (!curlv.empty()) {
            TreeNode* tmp = curlv.front(); curlv.pop();
            if (tmp->left)  nextlv.push(tmp->left);
            if (tmp->right) nextlv.push(tmp->right);
            if (curlv.empty()) res.push_back(tmp->val);
        }
    }
    return res;
}

};//DFS to add only one node (for each level)

class Solution { public: void dfs(TreeNode* ptr, int lv, vector &res){ if(!ptr) return; // Step 1. Every level has only one node (the far right node), // if current lv > res.size(), means we haven't added one node in this level to thre result. if(res.size() < lv) res.push_back(ptr->val);

    // Step 2. Add right child first, and then left, make sure the right most node is added first.
    if(ptr->right) dfs(ptr->right, lv+1, res);
    if(ptr->left)  dfs(ptr->left, lv+1, res);
}
vector<int> rightSideView(TreeNode* root) {
    vector<int> res;
    dfs(root, 1, res);
    return res;
}

};

[sync-by-unito[bot]]

➤ Nelson 3513 commented:

//124. Binary Tree Maximum Path Sum [Hard]

class Solution { public: int max_gain(TreeNode* root, int &maxSum) { if(!root) return 0;

    // Step 1. buttom up calculation to calculate one direction's max sum (maxOneDir)
    int l = max(max_gain(root->left, maxSum), 0); // at least 0
    int r = max(max_gain(root->right,maxSum), 0);

    // Step 2. start to build a /\ path if current node is included, update maxSum
    int newpath = root->val + l + r;
    maxSum = max(maxSum, newpath);

    // l, r at least 0, this reduces codes (compare to my old version)
    return root->val + max(l, r); 
}
int maxPathSum(TreeNode* root) {
    int maxSum = -2147483648;
    max_gain(root, maxSum);
    return maxSum;
}

};

[sync-by-unito[bot]]

➤ Nelson 3513 commented:

//297. Serialize and Deserialize Binary Tree

class Codec { public: // Encodes a tree to a single string. string serialize(TreeNode* root) { if(!root) return "#"; return to_string(root->val) + ',' + serialize(root->left) + ',' + serialize(root->right); }

// Decodes your encoded data to tree.
// https://www.techiedelight.com/split-string-cpp-using-delimiter/
TreeNode* dfs_deser(stringstream &ss){
    string node;
    getline(ss, node, ',');
    if(node == "#"){
        return NULL;
    }
    TreeNode* root = new TreeNode(stoi(node));
    root->left = dfs_deser(ss);
    root->right = dfs_deser(ss);
    return root;
}
TreeNode* deserialize(string data) {
    TreeNode *root;
    stringstream ss(data);
    return dfs_deser(ss);
}

};