298. (Locked)Binary Tree Longest Consecutive Sequence

Difficulty: Medium

Frequency: N/A

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

The path refers to any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The longest consecutive path need to be from parent to child (cannot be the reverse).

For example,

   1
    \
     3
    / \
   2   4
        \
         5

Longest consecutive sequence path is 3-4-5, so return 3.

   2
    \
     3
    / 
   2    
  / 
 1

Longest consecutive sequence path is 2-3,not 3-2-1, so return 2.

---

My solution:

Data structure:

Steps:

Complexity:

Runtime:

Space:

Test cases:

Corner cases:

Code:

class Solution {
public:
    int longestConsecutive(TreeNode* root) {
        return search(root, NULL, 0);
    }
    int search(TreeNode* node, TreeNode* parent, int len) {
        if (!node) return len;
        len = (parent && node->val == parent->val + 1) ? len + 1 : 1;
        return max(len, max(search(node->left, node, len), search(node->right, node, len)));
    }
};

---

Another solution:

Data structure:

steps:

Complexity:

Runtime:

Space:

Code:

---

Things to learn:

250. (Locked)Count Univalue Subtrees

Difficulty: Medium

Frequency: N/A

Given a binary tree, count the number of uni-value subtrees.

A Uni-value subtree means all nodes of the subtree have the same value.

For example:
Given binary tree,

              5
             / \
            1   5
           / \   \
          5   5   5

return 4.

---

My solution:

Data structure:

Steps:

Complexity:

Runtime:

Space:

Test cases:

Corner cases:

Code:

/**
 * 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:
    int countUnivalSubtrees(TreeNode* root) {
        int cnt = 0;
        countSubtree(root, cnt);
        return cnt;
    }
    bool countSubtree(TreeNode* node, int& cnt) {
        if (!node) return false;
        if (!node->left && !node->right) {
            cnt++;
            return true;
        }
        bool left = countSubtree(node->left, cnt);
        bool right = countSubtree(node->right, cnt);
        if (left && right && (!node->left || node->left->val == node->val) && (!node->right || node->right->val == node->val)) {
            cnt++;
            return true;
        }
        return false;
    }
}

---

Another solution:

Data structure:

steps:

Complexity:

Runtime:

Space:

Code:

---

Things to learn:

156. (Locked)Binary Tree Upside Down

Difficulty: Medium

Frequency: N/A

Given a binary tree where all the right nodes are either leaf nodes with a sibling (a left node that shares the same parent node) or empty, flip it upside down and turn it into a tree where the original right nodes turned into left leaf nodes. Return the new root.

For example:
Given a binary tree {1,2,3,4,5},

    1
   / \
  2   3
 / \
4   5

return the root of the binary tree [4,5,2,#,#,3,1].

   4
  / \
 5   2
    / \
   3   1

---

My solution:

Data structure:

Steps:

Complexity:

Runtime:

Space:

Test cases:

Corner cases:

Code:

class Solution {
    TreeNode* upsideDownBinaryTree(TreeNode* root) {
        if (!root) return NULL;
        TreeNode *node = root, right = NULL, parent = NULL;
        while (root) {
            TreeNode *left = node->left;
            node->left = right;
            right = node->right;
            node->right = parent;
            parent = node;
            node = left;
        }
        return parent;
    }
};

---

Another solution:

Data structure:

steps:

Complexity:

Runtime:

Space:

Code:

---

Things to learn:

285. (Locked)Inorder Successor in BST

Difficulty: Medium

Frequency: N/A

Given a binary search tree and a node in it, find the in-order successor of that node in the BST.

Note: If the given node has no in-order successor in the tree, return null.

---

My solution:

Data structure:

Steps:

Complexity:

Runtime:

Space:

Test cases:

Corner cases:

Code:

class Solution {
public:
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        if (!root || !p) return NULL;
        TreeNode *suc;
        while (root) {
            if (root->val <= p->val) root = root->right;
            else {
                suc = root;
                root = root->left;
            }
        }
        return suc;
    }
};

---

Another solution:

Data structure:

steps:

Complexity:

Runtime:

Space:

Code:

---

Things to learn:

333. (Locked)Largest BST Subtree

Difficulty: Medium

Frequency: N/A

Given a binary tree, find the largest subtree which is a Binary Search Tree (BST), where largest means subtree with largest number of nodes in it.

Note:
A subtree must include all of its descendants.
Here’s an example:

    10
    / \
   5  15
  / \   \ 
 1   8   7

The Largest BST Subtree in this case is the highlighted one.
The return value is the subtree’s size, which is 3.

Hint:

1. You can recursively use algorithm similar to 98. Validate Binary Search Tree at each node of the tree, which will result in O(nlogn) time complexity.

Follow up:
Can you figure out ways to solve it with O(n) time complexity?

---

My solution:

Data structure:

Steps:

Complexity:

Runtime:

Space:

Test cases:

Corner cases:

Code:

class Solution {
public:
    int largestBSTSubtree(TreeNode* root) {
        if (!root) return 0;
        if (!root->left && !root->right) return 1;
        if (isValid(root, NULL, NULL)) return count(root);
        return max(largestBSTSubtree(root->left), largestBSTSubtree(root->right));
    }
    bool isValid(TreeNode* node, TreeNode* min, TreeNode* max) {
        if (!node) return true;
        if (min && node->val <= min->val || max && node->val >= max->val) return false;
        return isValid(node->left, min, node) && isValid(node->right, node, max);
    }
    int count(TreeNode* node) {
        if (!node) return 0;
        if (!node->left && !node->right) return 1;
        return 1 + count(node->left) + count(node->right);
    }
};

---

Another solution:

Data structure:

steps:

Complexity:

Runtime:

Space:

Code:

---

Things to learn:

236. Lowest Common Ancestor of a Binary Tree

Difficulty: Medium

Frequency: N/A

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

        _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4

For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

---

My solution:

Data structure:

Steps:

Complexity:

Runtime:

Space:

Test cases:

Corner cases:

Code:

/**
 * 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:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (!root || root == p || root == q) return root;
        TreeNode *left = lowestCommonAncestor(root->left, p, q);
        TreeNode * right = lowestCommonAncestor(root->right, p, q);
        return !left ? right : !right ? left : root;
    }
};

---

Another solution:

Data structure:

steps:

Complexity:

Runtime:

Space:

Code:

---

Things to learn:

094. Binary Tree Inorder Traversal

Given a binary tree, return the inorder traversal of its nodes’ values.

For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [1,3,2].

Note: Recursive solution is trivial, could you do it iteratively?

---

Questions:

1. Recursive or iteratively

---

Test Cases:

1. [#] empty

2. [1] root only

3. [1, 2, #, 3, #, 4] all left

4. [1, #, 2, #, #, #, 3] all right

5. [1, #, 2, 3] normal

---

Solution 1:

Data structure:

vector, tree

Method:

Recursive:

1. helper(node->left)

2. push(node->val)

3. helper(node->right)

Complexity:

Runtime:

worst case: o(n^2)

average: o(nlogn)

Space:

o(n)

Code:

/**
 * 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> inorderTraversal(TreeNode* root) {
        vector<int> result;
        inorderTraverse(root, result);
        return result;
    }
    void inorderTraverse(TreeNode *node, vector<int>& result) {
        if (!node) return;
        inorderTraverse(node->left, result);
        result.push_back(node->val);
        inorderTraverse(node->right, result);
    }
};

---

 Solution 2:

Data structure:

Method:

Complexity:

Runtime:

Space:

Code:

---

Things to learn:

1. Tree Traversals:

https://fightingminionblog.wordpress.com/2017/07/25/tree-traversal/