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


  • 0
    F

    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;
        }
    };
    

  • 0

    @fight.for.dream Hi, I appreciate your posts. Perhaps posting to another category would be more appropriate?

    This category is strictly for interview questions only. Not for solution notes to practice problems. If this is indeed an interview question, please post only the problem description in the main post, and also add the company tag so I can move it to the correct subcategory. You can post the solution as a reply.


  • 0

    @fight.for.dream For the first problem, you should post it here.

    For the second problem, you should post it here.


  • 0
    F

    @1337c0d3r Sorry, I am summarizing all the related solution and to help me and my classmates to grasp all the related problem better, I hope you could allow us to keep this post for this month. Thanks a lot !


  • 0

    @fight.for.dream Not in this interview questions category. You can post it in the General Discussions category.


  • 0

    @fight.for.dream I have moved your topic to the General Discussions category. Thanks for your understanding as this will keep our forum organized.


  • 0
    F

    @1337c0d3r Thanks !!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.