Construct Binary Tree from Inorder and Postorder Traversal

Given inorder and postorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.


class Solution {
public:
    TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
        if (postorder.size()==0) return NULL;
        else
        {
            unordered_map<int, int> idxMap;
            int len = inorder.size();
           
            for (int i=0; i<len; i++)
            {
               idxMap[inorder[i]]=i;
            }
            int n = inorder.size()-1;
            return helper(inorder, postorder,0, n, n, idxMap);
        }
    }
   
    TreeNode *helper( vector<int> &inorder, vector<int> &postorder,int start, int end, int rIdx, unordered_map<int, int> &map)
    {
        if (start>end)
         return NULL;
        TreeNode *r = new TreeNode(postorder[rIdx]);
        int mid=map[postorder[rIdx]];
       
        r->left = helper(inorder,postorder,start,mid-1,rIdx-1-(end-mid), map);
// This index is what takes me most of time to figure out, need to find a way to rationalize it.
        r->right = helper(inorder,postorder,mid+1,end,rIdx-1, map);
       
        return r;
    }      
   
};

Construct Binary Tree from Preorder and Inorder Traversal (3 solutions)

Given preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.

This problem has 3 kinds of solutions.

1. Time complexity O(N^2)

class Solution {
public:
    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
        if (preorder.size()==0) return NULL;
        else
        return helper(preorder, inorder, 0, inorder.size()-1,0);
    }
   
    TreeNode *helper(vector<int> &preorder, vector<int> &inorder, int start, int end, int rIdx)
    {
        if (start>end)
         return NULL;
        TreeNode *r = new TreeNode(preorder[rIdx]);
        int mid=0;
        for (int i=start; i<=end; i++)
        {
            if (inorder[i]==preorder[rIdx])
            {
                mid = i;
                break;
            }
        }
       
        r->left = helper(preorder,inorder,start,mid-1,rIdx+1);
        r->right = helper(preorder, inorder,mid+1,end,rIdx+mid-start+1);
       
        return r;
    }
};


2. Using a hashtable to hash the index of inorder traversal will speed this up to O(N)
http://leetcode.com/2011/04/construct-binary-tree-from-inorder-and-preorder-postorder-traversal.html

class Solution {
public:
    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
        if (preorder.size()==0) return NULL;
        else
        {
            unordered_map<int, int> idxMap;
            int len = inorder.size();
           
            for (int i=0; i<len; i++)
            {
               idxMap[inorder[i]]=i;
            }
            return helper(preorder, inorder, 0, inorder.size()-1,0, idxMap);
        }
    }
   
    TreeNode *helper(vector<int> &preorder, vector<int> &inorder, int start, int end, int rIdx, unordered_map<int, int> &map)
    {
        if (start>end)
         return NULL;
        TreeNode *r = new TreeNode(preorder[rIdx]);
        int mid=map[preorder[rIdx]];
       
        r->left = helper(preorder,inorder,start,mid-1,rIdx+1, map);
        r->right = helper(preorder, inorder,mid+1,end,rIdx+mid-start+1, map);
       
        return r;
    }
};

3. The iterative solution that has O(N) time complexity
Idea:
1) Keep pushing the nodes from the preorder into a stack (and keep making
the tree by adding nodes to the left of the previous node) until the top of
the stack matches the inorder.

2) At this point, pop the top of the stack until the top does not equal
inorder (Use the popped node to note that you have made a pop).

3) Repeat 1 and 2 until preorder is empty. The key point is that whenever
the the popped node is NULL, insert a node to the right of the popped Node and reset popped Node to be NULL.

算法很巧妙。
我的理解是根据preorder inorder的基本原理，
1）能够保证左子树都入栈
2）3）中pop出来的node的左子树都在栈下面压着，所以在preorder里面的下一个肯定
是right child。
除了第一个元素外，其他每个元素进出栈一次，而且i,j各扫描pre,in一次。

class Solution {
public:
    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
        int i=0,j=0;
        TreeNode *root = new TreeNode(INT_MAX);
        TreeNode *pp = NULL, *ptr = root;
        stack<TreeNode *> st;
        st.push(root);
       
        while(j<inorder.size())
        {
            if (st.top()->val==inorder[j])
            {
                pp=st.top();
                st.pop();
                j++;
            }
            else if (pp){
                ptr = new TreeNode(preorder[i]);
                pp->right = ptr;
                pp=NULL;
                st.push(ptr);
                i++;
            }
            else {
                ptr=new TreeNode(preorder[i]);
                st.top()->left=ptr;
                st.push(ptr);
                i++;
            }
        }
        ptr=root->left;delete root;
        return ptr;       
    }
};

Reversing linked list iteratively and recursively

Will update this later.
1. Iterative,

Use a dummy node

2. Recursive
http://stackoverflow.com/questions/2434411/linked-list-recursive-reverse
http://www.ym910.com/wp/?p=4408

void RecursiveReverse(struct node** headRef) {

struct node* first;

struct node* rest;

if (*headRef == NULL) return; // empty list base case

first = *headRef; // suppose first = {1, 2, 3}

rest = first->next; // rest = {2, 3}

if (rest == NULL) return; // empty rest base case

RecursiveReverse(&rest); // Recursively reverse the smaller {2, 3} case

// after: rest = {3, 2}

first->next->next = first; // put the first elem on the end of the list

first->next = NULL; // (tricky step -- make a drawing)

*headRef = rest; // fix the head pointer

} 

Populating Next Right Pointers in Each Node II

Follow up for problem "Populating Next Right Pointers in Each Node".
What if the given tree could be any binary tree? Would your previous solution still work?
Note:

• You may only use constant extra space.

For example,
Given the following binary tree,

         1
       /  \
      2    3
     / \    \
    4   5    7

After calling your function, the tree should look like:

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \    \
    4-> 5 -> 7 -> NULL

1. Iterative: 非常巧妙地用了prev和next！

class Solution {
public:
    void connect(TreeLinkNode *root) {
       
        while(root)
        {
            TreeLinkNode *prev = NULL;
            TreeLinkNode *next = NULL;
           
            for ( ; root;root=root->next){
                if (next ==NULL)
                   next = root->left ? root->left : root->right;
                  
                if (root->left){
                    if (prev)
                        prev->next = root->left;
                    prev = root->left;
                }
               
                if (root->right){
                    if (prev)
                         prev->next = root->right;
                    prev = root->right;
                }
            }
            root = next;
        }
    }
};

2. Recursive 上级调试

class Solution {
public:
    void connect(TreeLinkNode *root) {
         if (root==NULL) return;
        
         TreeLinkNode dummy(-1);
         for (TreeLinkNode *cur = root, *prev=&dummy; cur; cur = cur->next)
         {
             if (cur->left!=NULL){
                 prev->next = cur->left;
                 prev = prev->next;
             }
            
             if (cur->right!=NULL){
                 prev->next = cur->right;
                 prev = prev->next;
             }
         }
         connect(dummy.next);
    
    }
};

Populating Next Right Pointers in Each Node

Given a binary tree

    struct TreeLinkNode {
      TreeLinkNode *left;
      TreeLinkNode *right;
      TreeLinkNode *next;
    }

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.
Initially, all next pointers are set to NULL.
Note:

• You may only use constant extra space.
• You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).

For example,
Given the following perfect binary tree,

         1
       /  \
      2    3
     / \  / \
    4  5  6  7

After calling your function, the tree should look like:

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \  / \
    4->5->6->7 -> NULL

Iterative:
class Solution {
public:
    void connect(TreeLinkNode *root) {
         if (root==NULL) return;
        
         TreeLinkNode *cur = root, *first=root;
         while(cur!=NULL)
         {
             if (cur->left)
               {
                   cur->left->next = cur->right;
                   if (cur->right)
                      { 
                          if (cur->next)
                          cur->right->next = cur->next->left;
                          else
                          cur->right->next = NULL;
                      }
               }
            if (cur->next)
            cur = cur->next;
            else
            {
            cur = first->left;
            first = cur;
            }
         }
    }
};

Recursive:

class Solution {
public:
    void connect(TreeLinkNode *root) {
        helper(root, NULL);
    }
   
    void helper (TreeLinkNode *cur, TreeLinkNode *sib)
    {
        if (cur==NULL)
            return;
        else
            cur->next = sib;
       
        helper(cur->left, cur->right);
       
        if (sib)
            helper(cur->right, sib->left);
        else
            helper(cur->right, NULL);
    }
};

Flatten Binary Tree to Linked List

Given a binary tree, flatten it to a linked list in-place.
For example,
Given

         1
        / \
       2   5
      / \   \
     3   4   6

The flattened tree should look like:

   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6

Hints:

If you notice carefully in the flattened tree, each node's right child points to the next node of a pre-order traversal.

I. Iterative solution

1. Find the right-most node of left child of cur
2. Set cur->right as the right-most node's right child
3. Set cur->left child as the right child
4. Set cur->left NULL
5. Set cur to be cur->right
6. Go to 1 until all nodes are flattened.

class Solution {
public:
    void flatten(TreeNode *root) {
        while(root){
            if (root->left){
                TreeNode *pre = root->left;
                while(pre->right)
                   pre = pre->right;
                pre->right = root->right;
                root->right = root->left;
                root->left = NULL;
            }
            root=root->right;
        }
    }
};

2.  把root 所代表树变成链表后，tail 跟在该链表后面
class Solution {
public:
    void flatten(TreeNode *root) {
        helper(root, NULL);
    }
   
    TreeNode *helper(TreeNode *root, TreeNode *tail){
        if (NULL==root) return tail;
       
        root->right = helper(root->left, helper(root->right, tail));
        root->left = NULL;
        return root;
    }
};

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.

class Solution {
public:
    bool isBalanced(TreeNode *root) {
        return helper(root)>=0;
    }
   
    int helper(TreeNode *root)
    {
        if (root==NULL) return 0;
       
        int left = helper(root->left);
        int right = helper(root->right);
       
        if (left<0||right<0||abs(left-right)>1) return -1;  //Pay attention to
        else
        return max(left, right)+1;           
    }
};

Pseudo code to write this in an iterative solution.

Two problems : Same Tree and Symmetric Tree

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

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

Same tree

Symmetric tree

class Solution { public:     bool isSameTree(TreeNode *p, TreeNode *q) {         if (p==NULL && q==NULL) return true;         if ((p!=NULL && q==NULL)||(p==NULL&&q!=NULL))            return false;                 if (p->val==q->val)         {             return isSameTree(p->left,q->left)&isSameTree(p->right,q->right);         }         else             return false;             } };     Iterative solution class Solution { public:     bool isSameTree(TreeNode *p, TreeNode *q) {         stack<TreeNode *> st;         st.push(p);         st.push(q);                 while(!st.empty())         {             p = st.top();st.pop();             q = st.top(); st.pop();                         if (p==NULL&&q==NULL) continue;             if (p==NULL||q==NULL) return false;             if (p->val==q->val)             {                 st.push(p->left);                 st.push(q->left);                                 st.push(p->right);                 st.push(q->right);             }             else             return false;                     }                 return true;     } };

class Solution { public:     bool helper(TreeNode *left, TreeNode *right)     {         if (left==right && left==NULL)             return true;         if ((left==NULL&&right!=NULL)||(left!=NULL && right==NULL))             return false;         return ((left->val==right->val)&&helper(left->left,right->right)&&helper(left->right, right->left));     }        bool isSymmetric(TreeNode *root) {         return root?helper(root->left, root->right):true;     } };        Iterative solution class Solution { public:     bool isSymmetric(TreeNode *root) {         if (root==NULL||(root->left==NULL&&root->right==NULL))             return true;                 TreeNode *p = root->left, *q=root->right;                 stack<TreeNode*> st;         st.push(p);         st.push(q);                 while(!st.empty())         {             p =st.top(); st.pop();             q = st.top(); st.pop();                         if (p==NULL&&q==NULL) continue;             if (p==NULL||q==NULL) return false;                         if (p->val!=q->val) return false;                         st.push(p->left);             st.push(q->right);                         st.push(p->right);             st.push(q->left);         }                 return true;     } };

A special post

On 9/12 nine years ago, I came to USA by plane. Time has gone so fast. Today, I've finished past half (77 out of 151) on the Leetcode problems! Cheer up!

Binary Tree Zigzag Level Order Traversal (To improve later)

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]
]

 vector<vector<int> > zigzagLevelOrder(TreeNode *root) {
        queue<TreeNode *> nextLevel;
        queue<TreeNode *> curLevel;
       
        TreeNode *r = root;
       
        vector<vector<int> > ret;
       
        if (r==NULL)
        return ret;
       
        curLevel.push(r);

        bool l2r=true;
       
        while(1)
        {
            vector<int> tmpV;
       
        while(!curLevel.empty())
        {
            TreeNode *tmp=curLevel.front();
           
            if (tmp!=NULL)
            {
                tmpV.push_back(tmp->val);
                if (tmp->left)
                 nextLevel.push(tmp->left);
                if (tmp->right)
                  nextLevel.push(tmp->right);
            }
           
            curLevel.pop();
        }
       
        if (!l2r)
           reverse(tmpV.begin(),tmpV.end());
          
        l2r=!l2r;
        ret.push_back(tmpV);
       
        if (nextLevel.empty())
        break;
        else
        {
        curLevel.swap(nextLevel);
        }
        }
       
        return ret;
    }

Recover Binary Search Tree (A solution using O(n) space )

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?

1. Recursive inorder traversal

a. 开始没想清楚怎么把那两个错误的node找出来
b. 应该用*& 的地方用了*。 后来发现不作为param来pass还更简单。

Writing this would work, *&      void helper(TreeNode *cur, TreeNode *&first, TreeNode *&second, TreeNode *&pre)    {        if (cur==NULL)            return;                   helper(cur->left, first, second, pre);        if (pre)        {          if (pre->val>cur->val)           {             if (first==NULL)              {                   first = pre;                   second = cur;              }             else                  second = cur;                     }        }          pre = cur;        helper(cur->right, first, second, pre);    }     void recoverTree(TreeNode *root) {         if (root==NULL||(root->left==NULL && root->right==NULL))         {             return;         }                 vector<TreeNode *> t;         TreeNode *first=NULL, *second=NULL, *pre=NULL;         helper(root,first, second, pre);           int tmp = first->val;         first->val = second->val;         second->val = tmp;               }

Not working, as the TreeNode * remains NULL Runtime Error!      void helper(TreeNode *cur, TreeNode *first, TreeNode *second, TreeNode *pre)    {        if (cur==NULL)            return;                   helper(cur->left, first, second, pre);        if (pre)        {        if (pre->val>cur->val)           {             if (first==NULL)              {                   first = pre;                   second = cur;              }             else                  second = cur;                     }        }        pre = cur;        helper(cur->right, first, second, pre);    }     void recoverTree(TreeNode *root) {         if (root==NULL||(root->left==NULL && root->right==NULL))         {             return;         }                 vector<TreeNode *> t;         TreeNode *first=NULL, *second=NULL, *pre=NULL;         helper(root,first, second, pre);           int tmp = first->val;         first->val = second->val;         second->val = tmp;               }

Then, after some research, writing those * out like the following produces much cleaner code and less head scratch about *&!!!     class Solution { public:     TreeNode *first, *second,  *pre;    void helper(TreeNode *cur)    {        if (cur==NULL)            return;                   helper(cur->left);        if (pre)        {          if (pre->val>cur->val)           {             if (first==NULL)              {                   first = pre;                   second = cur;              }             else                  second = cur;                     }           pre = cur;        }        else        pre = cur;        helper(cur->right);    }     void recoverTree(TreeNode *root) {         if (root==NULL||(root->left==NULL && root->right==NULL))         {             return;         }                 vector<TreeNode *> t;         first=NULL, second=NULL, pre=NULL;         helper(root);           int tmp = first->val;         first->val = second->val;         second->val = tmp;               } };

Binary Tree Traversal without Recursion 2

Morris Traversal

    vector<int> preorderTraversal(TreeNode *root) {
        vector<int> ret;
        TreeNode *cur=root, *prev=NULL;
       
        while(cur!=NULL){
            if (cur->left==NULL){
                ret.push_back(cur->val);
                cur = cur->right;
            }
            else{
                prev = cur->left;
               
                while(prev->right!=NULL && prev->right!=cur)
                prev = prev->right;
               
                if (prev->right==NULL){
                    ret.push_back(cur->val);
                    prev->right = cur;
                    cur = cur->left;
                }
                else{
                    prev->right=NULL;
                    cur = cur->right;
                }
            }
        }
       
        return ret;
    }

    vector<int> inorderTraversal(TreeNode *root) {
        vector<int> ret;
        TreeNode *cur=root, *prev=NULL;
       
        while(cur!=NULL){
            if (cur->left==NULL){
                ret.push_back(cur->val);
                cur = cur->right;
            }
            else{
                prev = cur->left;
               
                while(prev->right!=NULL && prev->right!=cur)
                prev = prev->right;
               
                if (prev->right==NULL){
                   
                    prev->right = cur;
                    cur = cur->left;
                }
                else{
                    ret.push_back(cur->val);
                    prev->right=NULL;
                    cur = cur->right;
                }
            }
        }
       
        return ret;       
    }

Binary Tree Traversal without Recursion 1

  
 vector<int> preorderTraversal(TreeNode *root) {
        stack<TreeNode*> st;
        vector<int> ret;
        if (root==NULL)
        return ret;
        TreeNode *r = root;
       
        while(r!=NULL||!st.empty())
        {
            while (r!=NULL)
            {
                st.push(r);
                ret.push_back(r->val);
                r=r->left;
            }
            r = st.top();
            st.pop();
            r=r->right;
        }
       
        return ret;
    }

    vector<int> inorderTraversal(TreeNode *root) {
        stack<TreeNode *> st;
        vector<int> ret;
        if (root==NULL)
        return ret;
        TreeNode *r = root;
       
        while(r||!st.empty())
        {
            while(r)
            {
                st.push(r);
                r = r->left;
            }
            TreeNode *tmp = st.top();
            st.pop();
            ret.push_back(tmp->val);
            r = tmp->right;
        }
       
        return ret;
    }

    vector<int> postorderTraversal(TreeNode *root) {
        vector<int> ret;
        if (root==NULL)
        return ret;
        stack<TreeNode *> st;
        TreeNode *r = root;
        TreeNode *lastVisitedNode=NULL;
        while(!st.empty()||r)
        {
            while(r)
            {
                st.push(r);
                r=r->left;
            }
           
            TreeNode *tmp = st.top();
            if (lastVisitedNode!=tmp->right&&tmp->right)
            r=tmp->right;
            else
            {
                st.pop();
                ret.push_back(tmp->val);
                lastVisitedNode = tmp;
            }
        }
        return ret;
    }