117. Populating Next Right Pointers in Each Node II

Difficulty: Hard

Frequency: N/A

Follow up for problem “Populating Next Right Pointers in Each Node“.

What if the given tree could be any binary tree? Would your previous solution still work?

Note:

  • You may only use constant extra space.

For example,
Given the following binary tree,

         1
       /  \
      2    3
     / \    \
    4   5    7

After calling your function, the tree should look like:

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \    \
    4-> 5 -> 7 -> NULL

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
/**
 * Definition for binary tree with next pointer.
 * struct TreeLinkNode {
 *  int val;
 *  TreeLinkNode *left, *right, *next;
 *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
 * };
 */
class Solution {
public:
    void connect(TreeLinkNode *root) {
        if (!root) return;
        root->next = NULL;
        TreeLinkNode *cur = root;
        while (cur) {
            TreeLinkNode *nn = cur;
            while (nn) {
                TreeLinkNode *ln = nn->left;
                TreeLinkNode *rn = nn->right;
                if (ln) {
                    if (rn) ln->next = rn;
                    else {
                        TreeLinkNode *tmp = nn;
                        while (tmp) {
                            if (!tmp->next) {
                                ln->next = NULL;
                                break;
                            } else if (tmp->next->left) {
                                ln->next = tmp->next->left;
                                break;
                            } else if (tmp->next->right) {
                                ln->next = tmp->next->right;
                                break;
                            }
                            tmp = tmp->next;
                        }
                    }
                }
                if (rn) {
                    TreeLinkNode *tmp = nn;
                    while (tmp) {
                        if (!tmp->next) {
                            rn->next = NULL;
                            break;
                        } else if (tmp->next->left) {
                            rn->next = tmp->next->left;
                            break;
                        } else if (tmp->next->right) {
                            rn->next = tmp->next->right;
                            break;
                        }
                        tmp = tmp->next;
                    }
                }
                nn = nn->next;
            }
            while (cur) {
                if (cur->left) {
                    cur = cur->left;
                    break;
                } else if (cur->right) {
                    cur = cur->right;
                    break;
                }
                cur = cur->next;
            }
        }
    }
};

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

098. Validate Binary Search Tree

Difficulty: Medium

Frequency: N/A

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

  • The left subtree of a node contains only nodes with keys less than the node’s key.
  • The right subtree of a node contains only nodes with keys greater than the node’s key.
  • Both the left and right subtrees must also be binary search trees.

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:
    bool isValidBST(TreeNode* root) {
        return checkBST(root, NULL, NULL);
    }
    bool checkBST(TreeNode* node, TreeNode* min, TreeNode* max) {
        if (!node) return true;
        if (min && node->val <= min->val || max && node->val >= max->val) return false;
        return checkBST(node->left, min, node) && checkBST(node->right, node, max);
    }
};

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

116. Populating Next Right Pointers in Each Node

Difficulty: Medium

Frequency: N/A

Given a binary tree

    struct TreeLinkNode {
      TreeLinkNode *left;
      TreeLinkNode *right;
      TreeLinkNode *next;
    }

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Note:

  • You may only use constant extra space.
  • You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).

For example,
Given the following perfect binary tree,

         1
       /  \
      2    3
     / \  / \
    4  5  6  7

After calling your function, the tree should look like:

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \  / \
    4->5->6->7 -> NULL

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
/**
 * Definition for binary tree with next pointer.
 * struct TreeLinkNode {
 *  int val;
 *  TreeLinkNode *left, *right, *next;
 *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
 * };
 */
class Solution {
public:
    void connect(TreeLinkNode *root) {
        if (!root) return;
        root->next = NULL;
        TreeLinkNode *cur = root;
        while (cur) {
            TreeLinkNode *nn = cur;
            while (nn) {
                TreeLinkNode *ln = nn->left;
                TreeLinkNode *rn = nn->right;
                if (ln) ln->next = rn;
                if (rn) {
                    if (nn->next) rn->next = nn->next->left;
                    else rn->next = NULL;
                }
                nn = nn->next;
            }
            cur = cur->left;
        }
    }
};

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

106. Construct Binary Tree from Inorder and Postorder Traversal

Difficulty: Medium

Frequency: N/A

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.


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* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if (inorder.empty() || postorder.empty() || inorder.size() != postorder.size()) return NULL;
        return generateTree(inorder, 0, inorder.size() - 1, postorder, 0, postorder.size() - 1);
    }
    TreeNode* generateTree(vector<int>& inorder, int is, int ie, vector<int>& postorder, int ps, int pe) {
        if (ps > pe) return NULL;
        TreeNode *node = new TreeNode(postorder[pe]);
        int mid = is;
        while (mid <= ie) {
            if (inorder[mid] == postorder[pe]) break;
            mid++;
        }
        node->left = generateTree(inorder, is, mid - 1, postorder, ps, ps + mid - is - 1);
        node->right = generateTree(inorder, mid + 1, ie, postorder, pe + mid - ie, pe - 1);
        return node;
    }
};

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

105. Construct Binary Tree from Preorder and Inorder Traversal

Difficulty: Medium

Frequency: N/A

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.


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* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if (preorder.empty() || inorder.empty() || preorder.size() != inorder.size()) return NULL;
        return generateTree(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1);
    }
    TreeNode* generateTree(vector<int>& preorder, int ps, int pe, vector<int>& inorder, int is, int ie) {
        if (ps > pe) return NULL;
        TreeNode *node = new TreeNode(preorder[ps]);
        int mid = is;
        while (mid <= ie) {
            if (inorder[mid] == preorder[ps]) break;
            mid++;
        }
        node->left = generateTree(preorder, ps + 1, ps + mid - is, inorder, is, mid - 1);
        node->right = generateTree(preorder, pe - ie + mid + 1, pe, inorder, mid + 1, ie);
        return node;
    }
};

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

109. Convert Sorted List to Binary Search Tree

Difficulty: Medium

Frequency: N/A

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
/**
 * 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* sortedListToBST(ListNode* head) {
        if (!head) return NULL;
        ListNode *fast = head, *slow = head, *pre = NULL;
        while(fast && fast->next) {
            fast = fast->next->next;
            pre = slow;
            slow = slow->next;
        }
        if (pre) pre->next = NULL;
        else head = NULL;
        TreeNode *root = new TreeNode(slow->val);
        root->left = sortedListToBST(head);
        root->right = sortedListToBST(slow->next);
        return root;
    }
};

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

114. Flatten Binary Tree to Linked List

Difficulty: Medium

Frequency: N/A

Given a binary tree, flatten it to a linked list in-place.

For example,
Given

         1
        / \
       2   5
      / \   \
     3   4   6

The flattened tree should look like:

   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6

click to show hints.

Hints:If you notice carefully in the flattened tree, each node’s right child points to the next node of a pre-order traversal.


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:
    void flatten(TreeNode* root) {
        TreeNode *cur = root;
        while(cur) {
            if (cur->left) {
                TreeNode *tmp = cur->left;
                while(tmp->right) {
                    tmp = tmp->right;
                }
                tmp->right = cur->right;
                cur->right = cur->left;
                cur->left = NULL;
            }
            cur = cur->right;
        }
    }
};

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn: