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


  • 0
    F

    *1 Construct BST from the given preorder traversal*

    Firsly, let us check the brute force solution, we just find the right substree range and construct both subtrees recursively .

    class Solution {
    public:
    	TreeNode* constructBSTfromPreorder(vector<int> preorder) {
    		int pos = 0;
    		int size = (int)preorder.size();
    		return dfs(preorder, pos, 0, size-1, size);
    	}
    
    	TreeNode* dfs(vector<int>& preorder, int& pos, int low, int high, int size) {
    		if (pos >= size || low > high)  return nullptr;
    		TreeNode* root = new TreeNode(preorder[pos]);
    		pos++;
    		if (low == high) 
    			return root;
    		//search for the start point for the right tree
    		int i;
    		for (i = low; i <= high; i++) {
    			if (preorder[i] > root->data) break;
    		}
    		root->left = dfs(predorder, pos, pos, i-1, size);
    		root->right = dfs(preorder, pos, i, high, size);
    		return root;
    	}
    };
    

    BUT inspired from the *Problem 98 --- Validate the Binary Search Tree's folllow solutions*

    class Solution {
    public:
        bool isValidBST(TreeNode* root) {
            return help(root, LONG_MIN, LONG_MAX);
        }
        
        bool help(TreeNode* root, long min_val, long max_val) {
            if (!root)  return true;
            if (root->val <= min_val || root->val >= max_val) {
                return false;
            }
            return help(root->left, min_val, root->val) && help(root->right, root->val, max_val);
        }
    };
    

    We can also using this range check ideas to Construct the binary search Tree in O(n) time .

    class Solution {
    public:
    	TreeNode* constructBSTfromPreorder(vector<int> preorder) {
    		int pos = 0;
    		int size = (int)preorder.size();
    		return dfs(preorder, pos, preorder[0], LONG_MIN, LONG_MAX, size);
    	}
    
    	TreeNode* dfs(vector<int>& preorder, int& pos, int key, int min, int max, int size) {
    		if (pos >= size) return nullptr;
    		TreeNode* root = nullptr;
    		if (key > min && key < max) {
    			root = new TreeNode(key);
    			pos++;
    			if (pos < size) {
    				root->left = dfs(preorder, pos, preorder[pos], min, key, size);
    				root->right = dfs(preorder, pos, preorder[pos], key, max, size);
    			}
    		}
    		return root;
    	}
    };
    

    We can also use stack to solve this problem ,

    class Solution {
    public:
    	TreeNode* constructBSTfromPreorder(vector<int> preorder) {
    		int pos = 0;
    		int size = (int)preorder.size();
    		stack<TreeNode*> st;
    		TreeNode* root = new TreeNode(preorder[0]);
    		st.push(root);
    		int i;
    		TreeNode* temp;
    		for (i = 1; i < size; i++) {
    			temp = nullptr;
    			//if the current value is bigger than the stack value, pop out it and record it, as it can be the parent node 
    			while (!st.empty() && preorder[i] > st.top()->val) {
    				temp = st.top();
    				st.pop();
    			}
    			//set the parent node
    			if (temp != nullptr) {
    				temp->right = new TreeNode(preorder[i]);
    				st.push(temp->right);
    			}
    			//set the left child relations
    			else {
    				TreeNode* cur = new TreeNode(preorder[i]);
    				st.top()->left = cur;
    				st.push(cur);
    			}
    		}
    		return root;
    	}
    };
    

    *Serialize and Deserialize a Binary Tree*

    • the Tree is Binary Search Tree (only use preorder is ok !)

    • the Tree is Complete Tree (level by level : 1-2-4-8)

    • Full Tree : every node has either 0 or 2 children, we just record a marker to mark it is leaf or internal node

    • we want to solve general binary tree

    The key is to record the NULL node as the marker

    class Codec {
    	string marker = "#";
    public:
    
        // Encodes a tree to a single string.
        string serialize(TreeNode* root) {
            ostringstream out;
            serialize(root, out, marker);
            return out.str();
        }
    
        // Decodes your encoded data to tree.
        TreeNode* deserialize(string data) {
            istringstream in(data);
            return deserialize(in, marker);
        }
    
        void serialize(TreeNode* root, ostringstream& out, string marker) {
        	if (root) {
        		out << root->val << ' ';
        		serialize(root->left, out, marker);
        		serialize(root->right, out, marker);
        	}
        	else {
        		out << marker << " ";
        	}
        }
    
        TreeNode* deserialize(istringstream& in, string marker) {
        	string val;
        	in >> val;
        	if (val == marker) 
        		return nullptr;
        	TreeNode* root = new TreeNode(stoi(val));
        	root->left = deserialize(in, marker);
        	root->right = deserialize(in, marker);
        	return root;
        }
    };
    

    *Serialize & Deserialize N-ary Tree*

    The key is to store an "end of children

    *The key is to store an "end of children " maker*

    Let us check the Solution

    class Codec {
    	int child_cnt = 5;
    	string marker;
    public:
    
        // Encodes a tree to a single string.
        string serialize(TreeNode* root) {
            ostringstream out;
            serialize(root, out, marker);
            return out.str();
        }
    
        // Decodes your encoded data to tree.
        TreeNode* deserialize(string data) {
            istringstream in(data);
            TreeNode* root;
            deserialize(root, in, marker);
            return root;
        }
    
        void serialize(TreeNode* root, ostringstream& out, char marker) {
        	if (root == nullptr) return;
        	out << root->val << ' ';
        	for (int i = 0; i < child_cnt && root->child[i]; i++) {
        		serialize(root->child[i], out, marker);
        	}
        	out << marker << " ";
        }
    
         int deserialize(TreeNode*& root, istringstream& in, char marker) {
        	string val;
        	in >> val;
        	//return 1 to mark that we have finished traversal of all the child nodes
        	if (val == marker) 
        		return 1;
        	root = new TreeNode(stoi(val));
        	for (int i = 0; i < child_cnt; i++) {
        		if (deserialize(root->child[i], in, marker))
        			break;
        	}
        	return 0;
        }
    };
    
    

    *Problem 331 Verify Preorder Serialization of A Binary Tree*

    One way to serialize a binary tree is to use pre-order traversal. When we encounter a non-null node, we record the node's value. If it is a null node, we record using a sentinel value such as #.

    Update : Here is a more clear solution provided by fff

    class Solution {
    public:
        vector<string> split(string str, char delim) {
            vector<string> result;
            stringstream ss(str);
            string line;
            while (getline(ss, line, delim)) {
                result.push_back(line);
            }
            return result;
        }
        bool isValidSerialization(string preorder) {
            vector<string> tokens = split(preorder,',');
            int nullCount = 0, nodeCount = 0;
            for (auto token: tokens) {
                if (nullCount >= nodeCount + 1) return false;
                if (token == "#") {
                    nullCount ++;
                } else {
                    nodeCount ++;
                }
            }
            return nullCount == nodeCount + 1;
        }
    };
    
    

    Solution : as we know the nullptr node are recorded as "#"

    class Solution {
    public:
        bool isValidSerialization(string preorder) {
            vector<string> elems;
            char delim = ',';
            split(preorder, delim, elems);
            vector<string> st;
            int index = 0;
            while (index < elems.size()) {
                st.push_back(elems[index++]);
                while (st.size() >= 3 && st[st.size() - 1] == "#" && st[st.size() - 2] == "#" && st[st.size() - 3] != "#") {
                    st.pop_back();
                    st.pop_back();
                    st.pop_back();
                    st.push_back("#");
                }
            }
            return st.size() == 1 && st[0] == "#";
        }
        
        void split(const string& s, char delim, vector<string>& elems) {
            stringstream ss(s);
            string item;
            while (getline(ss, item, delim)) {
                elems.push_back(item);
            }
        }
    };
    

    There is also a degree related solution :

    class Solution {
    public:
        bool isValidSerialization(string preorder) {
            if (preorder.empty()) return false;
            //split string to array of string 
            istringstream in(preorder);
            vector<string> v;
            string val;
            while(getline(in, val, ',')) v.push_back(val);
            //calculate the string array 
            int degree = 1;  
            for (int i = 0; i < v.size(); i++) {
                if (v[i] == "#") {
                    degree--;
                } else {
                    degree++;
                }
                if (i < (v.size()-1) && degree <= 0) return false;
            }
            return degree == 0;
        }
    };
    

    **Balanced Binary Tree**

    Here is the optimized solution :

    class Solution {
    public:
        bool isBalanced(TreeNode* root) {
            return dfs(root) != -1;
        }
        
        int dfs(TreeNode* root) {
            if (!root) return 0;
            int leftH = dfs(root->left);
            if (leftH == -1) return -1;
            int rightH = dfs(root->right);
            if (rightH == -1) return -1;
            if (abs(leftH - rightH) > 1) return -1;
            return max(leftH, rightH) + 1;
        }
    };
    

    Largest BST subtree -------- 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.

    Here is a update to help you better grasp the Largest BST and Extension Problem :

    Orginal

    class Solution {
    public:
        int largestBSTSubtree(TreeNode* root) {
            int res = 0, min_val = INT_MIN, max_val = INT_MAX;
            dfs(root, min_val, max_val, res);
            return res;
        }
    
        int dfs(TreeNode *root, int &mn, int &mx, int &res) {
              if (!root) return 0;
              if (min < root->val && max > root->val) {
                  int left_nodes = dfs(root->left, mn, root->val, res);
                  int right_nodes = dfs(root->right, root->val, mx, res);
                  if (left_nodes == -1 || right_nodes == -1) return -1;
                  int total_nodes = left_nodes + right_nodes + 1;
                  if (total_nodes > res) {
                    res = total_nodes;
                  }
                  return total_nodes;
              }
              else {
                  dfs(root, INT_MIN, INT_MAX, res);
                  return -1;
              }
        }
    };
    

    Extension

    class Solution {
    public:
        int largestBST(TreeNode* root) {
            int res = 0, min_val = INT_MIN, max_val = INT_MAX;
            dfs(root, min_val, max_val, res);
            return res;
        }
    
        int dfs(TreeNode *root, int &mn, int &mx, int &res) {
              if (!root) return 0;
              if (min < root->val && max > root->val) {
                  int left_nodes = dfs(root->left, mn, root->val, res);
                  //if (left_nodes == -1) return -1;
                  int right_nodes = dfs(root->right, root->val, mx, res);
                  //if (right_nodes == -1) return -1;
                  int total_nodes = left_nodes + right_nodes + 1;
                  if (total_nodes > res) {
                    res = total_nodes;
                  }
                  return total_nodes;
              }
              else {
                dfs(root, INT_MIN, INT_MAX, res);
                return 0;
              }
              //return -1;
        }
    };
    
    class Solution {
    public:
        int largestBSTSubtree(TreeNode* root) {
            int res = 0, min_val = INT_MIN, max_val = INT_MAX;
            bool d = isValidBST(root, min_val, max_val, res);
            return res;
        }
    
        bool isValidBST(TreeNode *root, int &mn, int &mx, int &res) {
        	if (!root) return true;
        	int left_size = 0, right_size = 0;
        	int left_min = INT_MIN, right_min = INT_MIN, left_max = INT_MAX, right_max = INT_MAX;
        	bool left_bst = isValidBST(root->left, left_min, left_max, left_size);
        	bool right_bst = isValidBST(root->right, right_min, right_max, right_size);
        	if (left_bst && right_bst) {
        		if ((!root->left || root->val >= left_max) && (!root->right || root->val <= right+min)) {
        			//if valid, update result
        			result = left_size + right_size + 1;
        			mn = root->left ? left_min : root->val;
        			mx = root->right ? right_max : root->val;
        			return true;
        		}
        	}
        	//if not valide, update result size to be the bigger one 
        	result = max(left_size, right_size);
        	return false;
        }
    };
    

    Here is an extension to this problem , the BST subtree can not contain subtree , which is more difficult than this one :

    /** 
    Given a binary tree, find the largest Binary Search Tree (BST), 
    where largest means BST with largest number of nodes in it. 
    The largest BST may or may not include all of its descendants.
    
    root -> left -> right (top to down method)
    
    **/
    
    int findLargestBST(BinaryTree *p, int min, int max, int &maxNodes, 
                       BinaryTree *& largestBST, BinaryTree *& child) {
      if (!p) return 0;
      if (min < p->data && p->data < max) {
        int leftNodes = findLargestBST(p->left, min, p->data, maxNodes, largestBST, child);
        BinaryTree *leftChild = (leftNodes == 0) ? NULL : child;
        int rightNodes = findLargestBST(p->right, p->data, max, maxNodes, largestBST, child);
        BinaryTree *rightChild = (rightNodes == 0) ? NULL : child;
    
        /** create the root node **/
        // create a copy of the current node and 
        // assign its left and right child.
        BinaryTree *parent = new BinaryTree(p->data);
        parent->left = leftChild;
        parent->right = rightChild;
        // pass the parent as the child to the above tree.
        child = parent;
        int totalNodes = leftNodes + rightNodes + 1;
        if (totalNodes > maxNodes) {
          maxNodes = totalNodes;
          largestBST = parent;
        }
        return totalNodes;
      } else {
        // include this node breaks the BST constraint,
        // so treat this node as an entirely new tree and 
        // check if a larger BST exist in this tree
        findLargestBST(p, INT_MIN, INT_MAX, maxNodes, largestBST, child);
        // must return 0 to exclude this node
        return 0;
      }
    }
    

    Problem --- Closest Binary Search Tree Value ------ Given a non-empty binary search tree and a target value, find the value in the BST that is closest to the target.

    //iterative solution 
    class Solution {
    public:
        int closestValue(TreeNode* root, double target) {
        	int result = root->val;
        	while (root) {
        		if (abs(result - target) >= abs(root->val - target)) {
        			result = root->val;
        		}
        		root = target < root->val ? root->left : root->right;
        	}
        	return result;
        }
    };
    //recursive solution 
    class Solution {
    public:
        int closestValue(TreeNode* root, double target) {
        	int a = root->val;
        	TreeNode* temp = target < a ? root->left : root->right;
        	if (!temp) return a;
        	int b = closetValue(t, target);
        	return abs(a-target) < abs(b-target) ? a : b;
        }
    };
    

    The following related problem have similar solution template !!!

    Closest Binary Search Tree Value 2 ------- Given a non-empty binary search tree and a target value, find k values in the BST that are closest to the target.

    class Solution {
    public:
        vector<int> closestKValues(TreeNode* root, double target, int k) {
            vector<int> res;
            dfs(root, target, k, res);
            return res;
        }
        void dfs(TreeNode *root, double target, int k, vector<int> &res) {
            if (!root) return;
            dfs(root->left, target, k, res);
            if (res.size() < k) res.push_back(root->val);
            else if (abs(root->val - target) < abs(res[0]-target)) {
            	res.erase(res.begin());
            	res.push_back(root->val);
            }
            else
            	return;
            dfs(root->right, target, k, res);
        }
    };
    

    Here is a min-heap based solution , share the similar ideas :

    class Solution {
    public:
        vector<int> closestKValues(TreeNode* root, double target, int k) {
            vector<int> res;
            priority_queue<pair<double, int>> q;
            inorder(root, target, k, q);
            while (!q.empty()) {
                res.push_back(q.top().second);
                q.pop();
            }
            return res;
        }
        void inorder(TreeNode *root, double target, int k, priority_queue<pair<double, int>> &q) {
            if (!root) return;
            inorder(root->left, target, k, q);
            q.push({abs(root->val - target), root->val});
            if (q.size() > k) q.pop();
            inorder(root->right, target, k, q);
        }
    };
    

    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.

    class Solution {
    private:
        TreeNode *pre = NULL, *suc = NULL;
    public:
        TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
            if (!p) return NULL;
            inorder(root, p);
            return suc;
        }
        void inorder(TreeNode *root, TreeNode *p) {
            if (!root) return;
            inorder(root->left, p);
            if (pre == p) suc = root;
            pre = root;
            inorder(root->right, p);
        }
    };
    

    Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

    class BSTIterator {
        stack<TreeNode*> bst_stack;
    private:
        void bst_push(TreeNode* cur) {
            while(cur) {
                bst_stack.push(cur);
                cur = cur->left;
            }
        }
    public:
        BSTIterator(TreeNode *root) {
            bst_push(root);
        }
    
        /** @return whether we have a next smallest number */
        bool hasNext() {
            return !bst_stack.empty();
        }
    
        /** @return the next smallest number */
        int next() {
            TreeNode* cur = bst_stack.top();
            bst_stack.pop();
            bst_push(cur->right);
            return cur->val;
        }
    };
    

  • 0
    F
    
    class Solution {
    public:
        int largestBSTSubtree(TreeNode* root) {
            int res = 0, min_val = INT_MIN, max_val = INT_MAX;
            dfs(root, min_val, max_val, res);
            return res;
        }
    
        bool dfs(TreeNode *root, int &cur_min, int &cur_max, int &res) {
            if (!root) return true;
            int left_cnt = 0, right_cnt = 0;
            int left_min = INT_MIN, left_max = INT_MAX;
            int right_min = INT_MIN, right_max = INT_MAX;
            bool left_bst = dfs(root->left, left_min, left_max, left_cnt);
            bool right_bst = dfs(root->right, right_min, right_max, right_cnt);
            if (left_bst && right_bst) {
                if ((!root->left || root->left >= left_max) && (!root->right || root->val <= right_min)) {
                    res = left_cnt + right_cnt + 1;
                    cur_min = root->left ? left_min : root->val;
                    cur_max = root->right ? right_max : root->val;
                    res = max(left_cnt, right_bst);
                    return true;
                } 
            }       
            return false;
        }
    };
    
    
    
    class Solution {
        int largestBST(TreeNode* root, int min_val, int max_val, int result, TreeNode*& largestBST, TreeNode*& child) {
            if (!root) return 0;
            if (min_val < root->val && root->val < max_val) {
                int left_cnt = largestBST(root->left, min_val, root->val, result, largestBST, child);
                TreeNode* left_child = (left_cnt == 0) ? nullptr : child;
                int right_cnt = largestBST(root->right, root->val, max_val, result, largestBST, child);
                TreeNode* right_child = (right_cnt == 0) ? nullptr : child;
                TreeNode* parent = new TreeNode(root->val);
                parent->left = left_child;
                parent->right = right_child;
                child = parent;
                int total_nodes = left_cnt + right_cnt + 1;
                if (total_nodes > result) {
                    result = total_nodes;
                    largestBST = parent;
                }
                return total_nodes;
            } else {
                largestBST(root, INT_MIN, INT_MAX, result, largestBST, child);
                return 0;
            }
        }
    };
    
    

Log in to reply
 

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