Thursday, September 25, 2014

[Leetcode] Binary Tree Level Order Traversal II

Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).
For example:
Given binary tree {3,9,20,#,#,15,7},
    3
   / \
  9  20
    /  \
   15   7
return its bottom-up level order traversal as:
[
  [15,7],
  [9,20],
  [3]
]
confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

Analysis:

class Solution {
public:
    vector<vector<int> > levelOrderBottom(TreeNode *root) {
        vector<vector<int> > ret;
        if (root == NULL)
            return ret;
        queue<TreeNode*> q;
        int currLevel = 1;
        int nextLevel = 0;
        q.push(root);
        vector<int> row;
        while(!q.empty())
        {
            TreeNode* t = q.front();
            q.pop();
            currLevel--;
            row.push_back(t->val);
            if (t->left != NULL)
            {
                q.push(t->left);
                nextLevel++;
            }
            if (t->right != NULL)
            {
                q.push(t->right);
                nextLevel++;
            }                
            
            if (currLevel == 0)
            {
                currLevel = nextLevel;
                nextLevel = 0;
                ret.insert(ret.begin(), row);
                row.clear();
            }
        }
        
        return ret;
    }
};

[Leetcode] Convert Sorted Array to Binary Search Tree

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

Analysis:

class Solution {
public:

    TreeNode *helper(vector &num, int b, int e) {
        if (b > e)
            return NULL;
        else
        {
            //middle as the root and recursively to construct the tree left and right
            int mid = (b+e)/2;
            TreeNode* root = new TreeNode(num[mid]);
            root->left = helper(num, b, mid - 1);
            root->right = helper(num, mid+1, e);
            return root;
        }
    }

    TreeNode *sortedArrayToBST(vector &num) {
        return helper(num, 0, num.size() - 1);
    }
};

[Leetcode] Convert Sorted List to Binary Search Tree

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

Analysis:

class Solution {
public:

    TreeNode *sortedListToBST(ListNode *head) {
        if (head == NULL)
            return NULL;
        
        if (head->next == NULL)
            return new TreeNode(head->val);
        
        //use fast and slow pointer to get the middle
        ListNode* fast = head;
        ListNode* slow = head;
        ListNode* prev = NULL;
        while(fast != NULL && fast->next != NULL)
        {
            prev = slow;
            fast = fast->next->next;
            slow = slow->next;
        }
        //divide the list into two part
        prev->next = NULL;
        //middle as the root
        TreeNode* root = new TreeNode(slow->val);
        //recursively convert the left and right node
        root->left = sortedListToBST(head);
        root->right = sortedListToBST(slow->next);
        return root;
    }
};

[Leetcode] Balanced Binary Tree

Given a binary tree, determine if it is height-balanced.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
Analysis:

Try to get the tree height and do the balance comparison in the same function to be more efficient.

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:

    int helper(TreeNode *root, bool& isBalanced)
    {
        if (root == NULL)
            return 0;
        else
        {
            int leftHeight = helper(root->left, isBalanced);
            int rightHeight = helper(root->right, isBalanced);
            if (abs(leftHeight - rightHeight) > 1)
                isBalanced = false;
                
            return max(leftHeight, rightHeight) + 1;
        }
    }

    bool isBalanced(TreeNode *root) {
        bool isBalanced = true;
        helper(root, isBalanced);
        return isBalanced;
    }
};

[Leetcode] Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
Analysis:

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int minDepth(TreeNode *root) {
        if (root == NULL)
            return 0;
        else if (root->left == NULL)
            return minDepth(root->right) + 1;
        else if (root->right == NULL)
            return minDepth(root->left) + 1;
        else
            return min(minDepth(root->left), minDepth(root->right)) + 1;
            
    }
};

[Leetcode] Path Sum

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
For example:
Given the below binary tree and sum = 22,
              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1
return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

Analysis:

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool hasPathSum(TreeNode *root, int sum) {
        if (root == NULL)
            return false;
        else if (root->left == NULL && root->right == NULL)
            return sum == root->val;
        else
            return hasPathSum(root->left, sum - root->val) ||
                hasPathSum(root->right, sum - root->val);
    }
};

[Leetcode] Path Sum II

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.
For example:
Given the below binary tree and sum = 22,
              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1
return
[
   [5,4,11,2],
   [5,8,4,5]
]
Analysis:

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:

    void helper(TreeNode *root, int sum, vector<vector<int> >& ret, vector<int>& nums)
    {
        if (root == NULL)
            return;
        //have to be leaft
        else if (root->left == NULL && root->right == NULL && sum == root->val)
        {
            //leaf number was not pushed yet
            nums.push_back(root->val);
            ret.push_back(nums);
            nums.pop_back();
        }
        else
        {
            nums.push_back(root->val);
            helper(root->left, sum - root->val, ret, nums);
            helper(root->right, sum - root->val, ret, nums);
            nums.pop_back();
        }
    }

    vector<vector<int> > pathSum(TreeNode *root, int sum) {
        vector<vector<int> > ret;
        vector<int> nums;
        helper(root, sum, ret, nums);
        
        return ret;
    }
};