C++ solution to Binary Tree Related Problem Set -2-

fight.for.dream

805

Given a binary tree, find the length of the longest consecutive sequence path.

class Solution {
public:
    int longestConsecutive(TreeNode* root) {
        if (!root) return 0;
        int res = 0;
        dfs(root, 1, res);
        return res;
    }
    void dfs(TreeNode *root, int len, int &res) {
        res = max(res, len);
        if (root->left) {
            if (root->left->val == root->val + 1) dfs(root->left, len + 1, res);
            else dfs(root->left, 1, res);
        }
        if (root->right) {
            if (root->right->val == root->val + 1) dfs(root->right, len + 1, res);
            else dfs(root->right, 1, res);
        }
    }
};

Here let us check a very clever BFS solution but not the DFS solution

class Solution {
public:
    int longestConsecutive(TreeNode* root) {
        if (!root) return 0;
        int res = 0;
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            int len = 1;
            TreeNode *t = q.front(); q.pop();
            while ((t->left && t->left->val == t->val + 1) || (t->right && t->right->val == t->val + 1)) {
                if (t->left && t->left->val == t->val + 1) {
                    if (t->right) q.push(t->right);
                    t = t->left;
                } else if (t->right && t->right->val == t->val + 1) {
                    if (t->left) q.push(t->left);
                    t = t->right;
                }
                ++len;
            }
            if (t->left) q.push(t->left);
            if (t->right) q.push(t->right);
            res = max(res, len);
        }
        return res;
    }
};

the path could include the path from root to leaf also could be leaf to root

class Solution {
int longestConsecutive2(TreeNode* root) {
    if (root == nullptr) return 0;
    int left = 0, left_big = 0,  left_small = 0;
    int right = 0, right_bit = 0, right_small = 0;
    dfs(root->left, root->val, left, left_big, left_small, root->val);
    dfs(root->right, root->val, right, right_big, right_small, root->val);
    int result = max(left, right, left_big + 1 + right_small, right_big + 1 + left_small);
    return result;
}

void dfs(TreeNode* root, int val, int& cnt, int& cnt_big, int& cnt_small, int prev_val) {
    if (root == nullptr) {
        cnt = 0;
        cnt_big = 0;
        cnt_small = 0;
        return;
    }

    int cnt_left, cnt_right, cnt_left_big, cnt_left_small, cnt_right_big, cnt_right_small;
    dfs(root->left, root->val, cnt_left, cnt_left_big, cnt_left_small, root->val);
    dfs(root->right, root->val, cnt_right, cnt_right_big, cnt_right_small, root->val);

    int result = max(cnt_left, cnt_right, cnt_left_big + 1 + cnt_right_small, cnt_right_big + 1 + cnt_left_small);

    if(root->val == prev_val + 1) {
        cnt = result;
        cnt_big = max(cnt_left_big, cnt_right_big) + 1;
        cnt_small = 0;
        return;
    }
    else if (root->val == prev_val - 1) {
        cnt = result;
        cnt_big = 0;
        cnt_small = max(cnt_left_small, cnt_right_small) + 1;
        return;
    }
    else {
        cnt = result;
        cnt_big = 0;
        cnt_small = 0;
        return;
    }
}

Verify Preorder Sequence in Binary Search Tree

The solution is a little bit tricky, let us check it, we just push the node input the stack, when we meet bigger value, we need to pop out and keep the record :

Here is O(N) space cost Solution

class Solution {
public:
    bool verifyPreorder(vector<int>& preorder) {
        int low = INT_MIN;
        stack<int> s;
        for (auto a : preorder) {
            if (a < low) return false;
            while (!s.empty() && a > s.top()) {
                low = s.top(); s.pop();
            }
            s.push(a);
        }
        return true;
    }
};

Here is a better solution like this : O(N) space cost, but we change the elements in the preorder array

class Solution {
public:
    bool verifyPreorder(vector<int>& preorder) {
        int low = INT_MIN, i = -1;
        for (auto a : preorder) {
            if (a < low) return false;
            while (i >= 0 && a > preorder[i]) {
                low = preorder[i--];
            }
            preorder[++i] = a;
        }
        return true;
    }
};

Count Uni-value Sub-trees --- Given a binary tree, count the number of uni-value subtrees.

Brute Force solution :

class Solution {
public:
    int countUnivalSubtrees(TreeNode* root) {
        if (!root) return res;
        if (isUnival(root, root->val)) ++res;
        countUnivalSubtrees(root->left);
        countUnivalSubtrees(root->right);
        return res;
    }
private:
    int res = 0;
    bool isUnival(TreeNode *root, int val) {
        if (!root) return true;
        return root->val == val && isUnival(root->left, val) && isUnival(root->right, val);
    }
};

Here is a optimized solution, we can do left->right->root traversal.

class Solution {
public:
    int countUnivalSubtrees(TreeNode* root) {
        int res = 0;
        isUnival(root, -1, res);
        return res;
    }

    bool isUnival(TreeNode *root, int val, int &res) {
        if (!root) return true;
        if (!isUnival(root->left, root->val, res) | !isUnival(root->right, root->val, res)) {
            return false;
        }
        ++res;
       return root->val == val;
    }
};

Binary Tree Upside Down

class Solution {
public:
    TreeNode *upsideDownBinaryTree(TreeNode *root) {
        if (!root || !root->left) return root;
        TreeNode *l = root->left, *r = root->right;
        TreeNode *res = upsideDownBinaryTree(l);
        l->left = r;
        l->right = root;
        root->left = NULL;
        root->right = NULL;
        return res;
    }
};

Comments (2)