[Leetcode] Gray Code

The gray code is a binary numeral system where two successive values differ in only one bit.

Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:

00 - 0
01 - 1
11 - 3
10 - 2

Note:
For a given n, a gray code sequence is not uniquely defined.

For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.

For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.

Analysis:

    vector<int> grayCode(int n) {
  
        vector<int> codes(1,0);
        for (int i = 0; i<n; i++)
        {
            for (int j=codes.size()-1; j >=0 ; j--)
            {
                int code = 0x1 << i | codes[j];
                codes.push_back(code);
            }
        }
        
        return codes;
    }

[Leetcode] Validate Binary Search Tree

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.

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

Analysis:

class Solution {
public:

    bool helper(TreeNode *root, int minVal, int maxVal) {
        if (root == NULL)
            return true;
        else
            return root->val < maxVal && 
            root->val > minVal &&
            helper(root->left, minVal, root->val) &&
            helper(root->right, root->val, maxVal);
        
    }

    bool isValidBST(TreeNode *root) {
        return helper(root, INT_MIN, INT_MAX);
    }
};

[Leetcode] Recover Binary Search Tree

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Note:
A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

Analysis:

For BST, the inorder traversal will get the list of elements in sorted order. If two elements were swapped, there are two cases, the elements are next to each other or not. 

1,  2,  5,  4,  3,  6

         ^p1     ^p2

1,  2,  4,  3,  5,  6

          ^p1^p2

Doing an inorder traversal and the elements are marked as p1 and p2 if current element is less than previous element.   

class Solution {
public:

    void helper(TreeNode *root, TreeNode* &prev, TreeNode* &p1, TreeNode* &p2) {
        if (root == NULL)
            return;
        
        helper(root->left, prev, p1, p2);
            
        if (prev != NULL && root->val < prev->val)
        {
            if (p1 == NULL)
            {
                p1 = prev;
                p2 = root;
            }
            else
            {
                p2 = root;
            }
        }
        
        prev = root;
        
        helper(root->right, prev, p1, p2);
    }

    void recoverTree(TreeNode *root) {
        TreeNode *prev = NULL;
        TreeNode *p1 = NULL;
        TreeNode *p2 = NULL;
        
        helper(root, prev, p1, p2);
        
        swap(p1->val, p2->val);
    }
};

[Leetcode] Same Tree

Given two binary trees, write a function to check if they are equal or not.

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

Analysis:

class Solution {
public:
    bool isSameTree(TreeNode *p, TreeNode *q) {
        if (p == NULL && q == NULL)
            return true;
        else if (p == NULL || q == NULL)
            return false;
        else
        {
            return p->val == q->val && 
            isSameTree(p->left, q->left) &&
            isSameTree(p->right, q->right);
        }
    }
};

[Leetcode] Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree is symmetric:

    1
   / \
  2   2
 / \ / \
3  4 4  3

But the following is not:

    1
   / \
  2   2
   \   \
   3    3

Note:
Bonus points if you could solve it both recursively and iteratively.

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

Analysis:

class Solution {
public:

    bool helper(TreeNode *left, TreeNode* right) {
        if (left == NULL && right == NULL)
            return true;
        else if (left == NULL || right == NULL)
            return false;
        else
        {
            return left->val == right->val 
            && helper(left->left, right->right)
            && helper(left->right, right->left);
        }
    }
    bool isSymmetric(TreeNode *root) {
        if (root == NULL)
            return true;
        else
            return helper(root->left, root->right);
    }
};

[Leetcode] Binary Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

[
  [3],
  [9,20],
  [15,7]
]

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

Analysis:

class Solution {
public:
    vector<vector<int> > levelOrder(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.push_back(row);
                row.clear();
            }
        }
        
        return ret;        
    }
};

[Leetcode] Binary Tree Zigzag Level Order Traversal

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:

[
  [3],
  [20,9],
  [15,7]
]

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

Analysis:

class Solution {
public:
    vector<vector<int> > zigzagLevelOrder(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;
        int level = 1;
        while(!q.empty())
        {
            TreeNode* t = q.front();
            q.pop();
            currLevel--;
            if (level % 2 == 1)
                row.push_back(t->val);
            else
                row.insert(row.begin(), t->val);
            if (t->left != NULL)
            {
                q.push(t->left);
                nextLevel++;
            }
            if (t->right != NULL)
            {
                q.push(t->right);
                nextLevel++;
            }                
            
            if (currLevel == 0)
            {
                level++;
                currLevel = nextLevel;
                nextLevel = 0;
                ret.push_back(row);
                row.clear();
            }
        }
        
        return ret;        
    }
};