Tree

Binary Search Tree

36. 235. Lowest Common Ancestor of a Binary Search Tree

/**
 * 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->val > p->val && root->val > q->val) {
            return lowestCommonAncestor(root->left, p, q);
        } else if (root->val < p->val && root->val < q->val) {
            return lowestCommonAncestor(root->right, p, q);
        } else {
            return root;
        }
    }
};

37. Validate Binary Search Tree

TODO

38. 230. Kth Smallest Element in a BST

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int K;
    public int kthSmallest(TreeNode root, int k) {
        K = k;
        return inorder(root);
    }

    private Integer inorder(TreeNode cur) {
        if (cur == null)
            return null;
        Integer left = inorder(cur.left);
        if (left == null) {
            if (--K == 0)
                return cur.val;
            else
                return inorder(cur.right);
        }
        return left;
    }
}

Binary Tree

39. 226. Invert Binary Tree

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        invertTree(root.left);
        invertTree(root.right);
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        return root;
    }
}

40. 110. Balanced Binary Tree

Double check how to implement post-order visiting using iterative way.

class Solution {
public:
    bool isBalanced(TreeNode* root) {
        return isBalancedIterative(root);
    }

    bool isBalancedRecursive(TreeNode* root) {
        if (helper(root) == -1) {
            return false;
        }
        return true;
    }

    int helper(TreeNode* node) {
        if (!node) {
            return 0;
        }
        int leftHeight = helper(node->left);
        int rightHeight = helper(node->right);
        if (abs(leftHeight - rightHeight) > 1) {
            return -1;
        } else if (leftHeight == -1 || rightHeight == -1) {
            return -1;
        } else {
            return max(leftHeight, rightHeight) + 1;
        }
    }

    bool isBalancedIterative(TreeNode* root) {
        if (!root) return true;
        
        std::stack<TreeNode*> stack;
        std::unordered_map<TreeNode*, int> heights;
        TreeNode* lastVisited = nullptr;
        TreeNode* current = root;
        
        while (!stack.empty() || current) {
            // Reach the leftmost node
            while (current) {
                stack.push(current);
                current = current->left;
            }
            
            current = stack.top();
            
            // If the right child exists and is not yet visited, visit it
            if (current->right && lastVisited != current->right) {
                current = current->right;
            } else {
                stack.pop();
                int leftHeight = heights.count(current->left) ? heights[current->left] : 0;
                int rightHeight = heights.count(current->right) ? heights[current->right] : 0;
                
                // Check if the current node is balanced
                if (std::abs(leftHeight - rightHeight) > 1) {
                    return false;
                }
                
                // Store the height of the current node
                heights[current] = 1 + std::max(leftHeight, rightHeight);
                lastVisited = current;
                current = nullptr;
            }
        }
        
        return true;
    }
};

41. Binary Tree Level Order Traversal

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> results;
        if (!root) {
            return results;
        }
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()) {
            int size = q.size();
            vector<int> tmp;
            for (int i = 0; i < size; i++) {
                TreeNode* n = q.front();
                tmp.push_back(n->val);
                if (n->left) {
                    q.push(n->left);
                } 
                if (n->right) {
                    q.push(n->right);
                }
                q.pop();
            }
            results.push_back(tmp);
        }
        return results;
    }
};

42. 236. Lowest Common Ancestor of a Binary Tree

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        if (root == p || root == q) {
            return root;
        }

        TreeNode l = lowestCommonAncestor(root.left, p, q);
        TreeNode r = lowestCommonAncestor(root.right, p, q);

        if (l != null && r != null) {
            return root;
        } else if (l != null) {
            return l;
        } else {
            return r;
        }
    }
}

43. 297. Serialize and Deserialize Binary Tree

/**
 * 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) {
        if (!root) {
            return "x,";
        }   
        return to_string(root->val) + "," + serialize(root->left) + serialize(root->right);
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        queue<string> q;
        string s;
        for (int i = 0; i < data.size(); i++) {
            if (data[i] == ',') {
                q.push(s);
                s = "";
                continue;
            }
            s += data[i];
        }
        if (s.size() != 0) {
            q.push(s);
        }
        
        return deserialize_helper(q);
    }

    TreeNode* deserialize_helper(queue<string> &q) {
        string s = q.front();
        q.pop();
        if (s == "x") {
            return NULL;
        }
        TreeNode* root = new TreeNode(stoi(s));
        root->left = deserialize_helper(q);
        root->right = deserialize_helper(q);
        return root;
    }
};

// Your Codec object will be instantiated and called as such:
// Codec ser, deser;
// TreeNode* ans = deser.deserialize(ser.serialize(root));

44. 543. Diameter of Binary Tree

class Solution {
private:
    int result;    
public:
    int diameterOfBinaryTree(TreeNode* root) {
        iterative(root);
        return result;
    }

    void iterative(TreeNode* node) {
        stack<TreeNode*> s;
        TreeNode* current = node;
        TreeNode* lastVisited = nullptr;
        unordered_map<TreeNode*, int> heights;

        while (!s.empty() || current) {
            while (current) {
                s.push(current);
                current = current->left;
            }
            current = s.top();

            if (current->right && current->right != lastVisited) {
                current = current->right;
            } else {
                s.pop();
                int left = heights.count(current->left) ? heights[current->left] : 0;
                int right = heights.count(current->right) ? heights[current->right] : 0;
                result = max(result, left + right); // post-order
                heights[current] = max(left, right) + 1;
                lastVisited = current;
                current = nullptr;
            }
        }
    }

    int recursive(TreeNode* node) {
        if (!node) {
            return 0;
        }

        int left = recursive(node->left);
        int right = recursive(node->right);
        result = max(result, left + right); // post-order
        return max(left, right) + 1;
    }
};

45. 199. Binary Tree Right Side View

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Map<Integer, Boolean> marked = new HashMap<>();
        rightSideRecursive(result, root, marked, 0);
        return result;
    }

    public void rightSideRecursive(List<Integer> result, TreeNode cur, Map<Integer, Boolean> marked, int level) {
        if (cur == null) {
            return;
        }
        if (!marked.getOrDefault(level, false)) {
            marked.put(level, true);
            result.add(cur.val);
        }
        rightSideRecursive(result, cur.right, marked, level+1);
        rightSideRecursive(result, cur.left, marked, level+1);
    }
}

46. Maximum Depth of Binary Tree

class Solution {
public:
    int maxDepth(TreeNode* root) {
        return helper(root);
    }

    int helper(TreeNode *node) {
        if (!node) {
            return 0;
        }
        return max(helper(node->left), helper(node->right)) + 1;
    }
};

class Solution {
    public int maxDepth(TreeNode root) {
        Stack<TreeNode> s = new Stack<>();
        TreeNode current = root;
        TreeNode last = null;
        Map<TreeNode, Integer> h = new HashMap<>();

        while (!s.empty() || current != null) {
            while (current != null) {
                s.push(current);
                current = current.left;
            }
            current = s.peek();
            if (current.right != null && last != current.right) {
                current = current.right;
            } else {
                s.pop();
                // post-order visit
                int left = h.containsKey(current.left) ? h.get(current.left) : 0;
                int right = h.containsKey(current.right) ? h.get(current.right) : 0;
                h.put(current, (int)(Math.max(left, right) + 1));
                last = current;
                current = null;
            }
        }
        return h.get(root);
    }
}

47. Construct Binary Tree from Preorder and Inorder Traversal

TODO