Tag: tree

222. Count Complete Tree Nodes

fightingminionLeave a comment

Difficulty: Medium

Frequency: N/A

Given a complete binary tree, count the number of nodes.

Definition of a complete binary tree from Wikipedia:
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

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 countNodes(TreeNode* root) {
        int cnt = 0, h = height(root);
        while (root) {
            if (height(root->right) == h - 1) {
                cnt += 1 << h;
                root = root->right;
            } else {
                cnt += 1 << h - 1;
                root = root->left;
            }
            h--;
        }
        return cnt;
    }
    int height(TreeNode* node) {
        return !node ? -1 : 1 + height(node->left);
    }
};
Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:
Things to learn:

297. Serialize and Deserialize Binary Tree

fightingminionLeave a comment

Difficulty: Medium

Frequency: N/A

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

For example, you may serialize the following tree

    1
   / \
  2   3
     / \
    4   5

as "[1,2,3,null,null,4,5]", just the same as how LeetCode OJ serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

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 Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        ostringstream out;
        serializing(root, out);
        return out.str();
    }

    TreeNode* deserialize(string data) {
        istringstream in(data);
        return deserializing(in);
    }
private:
    void serializing(TreeNode* root, ostringstream& out) {
        if (root) {
            out << root->val << " ";
            serializing(root->left, out);
            serializing(root->right, out);
        } else out << "# ";
    }
    TreeNode* deserializing(istringstream& in) {
        string val;
        in >> val;
        if (val == "#") return NULL;
        TreeNode *root = new TreeNode(stoi(val));
        root->left = deserializing(in);
        root->right = deserializing(in);
        return root;
    }
};

// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));
Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:
Things to learn:

145. Binary Tree Postorder Traversal

fightingminion2 Comments

Difficulty: Hard

Frequency: N/A

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

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

   1
    \
     2
    /
   3

return [3,2,1].

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

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:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        dfs(root, result);
        return result;
    }
    void dfs(TreeNode* node, vector<int>& result) {
        if (!node) return;
        dfs(node->left, result);
        dfs(node->right, result);
        result.push_back(node->val);
    }
};
Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:
Things to learn:

272. (Locked)Closest Binary Search Tree Value II

fightingminionLeave a comment

Difficulty: Hard

Frequency: N/A

Given a non-empty binary search tree and a target value, find k values in the BST that are closest to the target.

Note:

  • Given target value is a floating point.
  • You may assume k is always valid, that is: k ≤ total nodes.
  • You are guaranteed to have only one unique set of k values in the BST that are closest to the target.

Follow up:
Assume that the BST is balanced, could you solve it in less than O(n) runtime (where n = total nodes)?

Hint:

  1. Consider implement these two helper functions:
    1. getPredecessor(N), which returns the next smaller node to N.
    2. getSuccessor(N), which returns the next larger node to N.
  2. Try to assume that each node has a parent pointer, it makes the problem much easier.
  3. Without parent pointer we just need to keep track of the path from the root to the current node using a stack.
  4. You would need two stacks to track the path in finding predecessor and successor node separately.
My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
    vector<int> closestKValues(TreeNode* root, double target, int k) {
        priority_queue<pair<double, int>> pq;
        vector<int> result;
        dfs(root, pq, target, k);
        while (!pq.empty()) {
            result.push_back(pq.top().second);
            pq.pop();
        }
        return result;
    }
    void dfs(TreeNode* node, priority_queue<pair<double, int>>& pq, double target, int k) {
        if (!node) return;
        pq.push(make_pair(abs(target - (double)node->val), node->val));
        if (pq.size() > k) pq.pop();
        dfs(node->left, pq, target, k);
        dfs(node->right, pq, target, k);
    }
};
Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:
Things to learn:

298. (Locked)Binary Tree Longest Consecutive Sequence

fightingminionLeave a comment

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

fightingminionLeave a comment

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

fightingminionLeave a comment

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

fightingminionLeave a comment

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

fightingminionLeave a comment

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

fightingminionLeave a comment

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: