Recursion

21. Merge Two Sorted Lists

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (!l1) return l2;
        if (!l2) return l1;
        if (l1->val < l2->val) {
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        } else {
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
    }
};

110. Balanced Binary Tree

class Solution {
public:
    bool isBalanced(TreeNode* root) {
        bool isbalance = true;
        return -1 != get_height(root, isbalance);
    }

    int get_height(TreeNode* root, bool& isbalance) {
        if (!isbalance) return -1;
        if (!root) return 0;
        int left = get_height(root->left, isbalance);
        int right = get_height(root->right, isbalance);
        if (left == -1 || right == -1 || abs(left - right) > 1) {
            isbalance = false;
            return -1;
        }
        return 1 + max(left, right);
    }
};

124. Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path does not need to go through the root.

For example:
Given the below binary tree,

       1
      / \
     2   3

Return 6.

class Solution {
    int maxToRoot(TreeNode *root, int &re) {
        if (!root) return 0;
        int l = maxToRoot(root->left, re);
        int r = maxToRoot(root->right, re);
        if (l < 0) l = 0;
        if (r < 0) r = 0;
        if (l + r + root->val > re) re = l + r + root->val;
        return root->val += max(l, r);
    }
public:
    int maxPathSum(TreeNode *root) {
        int res = INT_MIN;
        maxToRoot(root, res);
        return res;
    }
};

333 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.

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:

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?

class Solution {
public:
    int largestBSTSubtree(TreeNode* root) {
        int res = 0;
        long min_val, max_val;
        isBST(root, min_val, max_val, res);
        return res;
    }

    bool isBST(TreeNode* root, long &min_val, long &max_val, int& res) {
        if (!root) return true;
        int left_cnt = 0;
        int right_cnt = 0;
        long lmin,lmax, rmin, rmax;

        bool left = isBST(root->left, lmin, lmax, left_cnt);
        bool right = isBST(root->right, rmin, rmax, right_cnt);
        bool inrange = (!root->left || root->val >= lmax) && (!root->right || root->val <= rmin);
        if (left && right && inrange) {
            res = left_cnt + right_cnt + 1;
            min_val = root->left ? lmin : root->val;
            max_val = root->right ? rmax : root->val;
            return true;
        }
        res = max(left_cnt, right_cnt);
        return false;
    }
};