LeetCode Problem:Flatten Binary Tree to Linked List

We can notice that in the flattened tree, each sub node is the successor node of it’s parent node in the pre-order of the original tree. So, we can do it in recursive manner, following the steps below:
1.if root is NULL return;
2.flatten the left sub tree of root, if there is left sub-tree;
3.flatten the right sub-tree of root, if has;
4.if root has no left sub-tree, then root is flattened already, just return;
5.we need to merge the left sub-tree with the right sub-tree, by concatenate the right sub-tree to the last node in left sub-tree.
5.1.find the last node in the left sub tree, as the left is flattened, this is easy.
5.2.concatenate the right sub-tree to this node’s right child.
5.3.move the left sub-tree to the right for root.
5.4.clear the left child of root.
6.done.

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



Code:48ms to accept with large test set.

/**
 * 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 flatten(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (root == NULL) return;
        //1.flat the left subtree
        if (root->left)
            flatten(root->left);
        //2.flatten the right subtree
        if (root->right)
            flatten(root->right);
        //3.if no left return
        if (NULL == root->left)
            return;
        //4.insert left sub tree between root and root->right
        //4.1.find the last node in left
        TreeNode ** ptn = & (root->left->right);
        while (*ptn)
            ptn = & ((*ptn)->right);
        //4.2.connect right sub tree after left sub tree
        *ptn = root->right;
        //4.3.move left sub tree to the root's right sub tree
        root->right = root->left;
        root->left = NULL;
        
    }
};



Code rewrite at 2013-2-20, non-recursive version

class Solution {
public:
    void flatten(TreeNode *root) {
        bool f = true;
        stack t;
        TreeNode *pre = NULL;
        if(root) {
            t.push(root);
        }
        
        while(t.size()) {
            TreeNode *cur = t.top();
            if(f) {
                if(cur->left && cur->left != pre) {
                    t.push(cur->left);
                } else {
                    f = false;
                }
            } else {
                if(cur->right && cur->right != pre) {
                    t.push(cur->right);
                    f = true;
                } else {
                    t.pop();
                    //at this time, the sub-tree of cur is flattened, so just flatten the cur
                    TreeNode *left = cur->left;
                    if(left) {
                        TreeNode *lastLeft = left;
                        while(lastLeft->right) {
                            lastLeft = lastLeft->right;
                        }
                        lastLeft->right = cur->right;
                        cur->right = left;
                        cur->left = NULL;
                    }
                }
            }
            pre = cur;
        }
    }
};

LeetCode题目:Convert Sorted List to Binary Search Tree

问题比上一个难一点,如果是可以用O(n)空间的话,倒是可以开一个数组放上这n个数,然后按上一个问题的解法去做。总体时间O(n),空间O(n)。

不过这题这样出应该不是这个意思。假如不用O(n)空间的话:
可以先数一下一共有多少个节点。O(n)时间。
然后去找到根节点(数数),然后根节点之前是左子树,之后是右子树,并且两个子树的节点个数都是可以直接计算出来的,递归解这个问题就可以了。
那么总体时间复杂度是O(n*logn),空间O(logn)



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.



代码:114ms过大集合

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
    TreeNode *formTree(ListNode *head, int count) {
        if(count <= 0) return NULL;
        int rootIndex = count / 2;
        ListNode *rootNode = head;
        for(int ir = 0; ir < rootIndex; ++ir) {
            rootNode = rootNode->next;
        }
        TreeNode *root = new TreeNode(rootNode->val);
        root->left = formTree(head,rootIndex);
        root->right = formTree(rootNode->next, count - rootIndex - 1);
        return root;
    }
public:
    TreeNode *sortedListToBST(ListNode *head) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        
        //1. find the node count, takes O(n) time
        int nodeCount = 0;
        for(ListNode *cur = head; cur != NULL; cur = cur->next) {
            ++nodeCount;
        }
        
        //2. form the tree with the middle as the root
        return formTree(head, nodeCount);
    }
};

CCI题目2-5:Find Loop

建一个hash来做,从前往后扫描,遇到重复的输出就可以了。(findLoop)
最后有c++中map的简单实用例子。



另外cci上写了一个更有意思的算法,就是两个指针在链表上跑,一个快一个慢,慢的跑一步,快的跑两步。
当他们相遇的时候,让快的那个到链表开头,然后两个指针以相等的速度(一比一),继续跑,再次相遇的时候就是loop的开始点。

为什么?
假设有一个n米长的环形跑道,两个人一快一慢(2:1)从同一个起点开跑。下次相遇在哪儿?起点,而且是快的跑了两圈,慢的一圈。
进一步,如果快的那个先跑了k米呢?那他们应该相遇在距起点k米的位置。因为Sl = t, Sh = 2t + k,而令Sh = Sl + pn,可以得到t = pn – k。也就是他们总会在这个位置相遇。
所以此时让快的那个回到起点,(起点正好距循环开始k米),下次相遇,就是循环开始点。
这个想法很巧(findLoopEx)



题目
Given a circular linked list, implement an algorithm which returns node at the begin- ning of the loop.
DEFINITION
Circular linked list: A (corrupt) linked list in which a node’s next pointer points to an earlier node, so as to make a loop in the linked list.
EXAMPLE
input: A -> B -> C -> D -> E -> C [the same C as earlier]
output: C



代码

<

pre>
Node * findLoop(Node *pHead) {
map exmap;
while (pHead) {
if (exmap.find(pHead) != exmap.end()) {
return pHead;
}
exmap[pHead] = true;
pHead = pHead->next;
}
return NULL;
}

Node *findLoopEx(Node *pHead) {
Node *pRunner = pHead;
Node *pWalker = pHead;
int step = 0;

//each step of walker, runner goes two.
while (pRunner) {
    pRunner = pRunner->next;
    if (++step == 2) {
        pWalker = pWalker->next;
        step = 0;
        if (pRunner == pWalker) {
            break;
        }
    }
}
if (!pRunner) {
    return NULL;//no loop
}
//then they meet at the k posotion before loop started
//and the k is nodes before loop start
//so let runner back to head and with speed of 1
//they go simutaniously, when next meet, that position is the loop start point
pRunner = pHead;
while (pWalker) {
    if (pWalker == pRunner) {
        return pWalker;
    }
    pWalker = pWalker->next;
    pRunner = pRunner->next;
}
return NULL;//something wrong

}

int main(int argc, const char * argv[])
{
cout<<“Hello\n”;
Node *phead = loopList(10, 8);
printList(phead);
cout<<“process…”<<endl;
Node *pLoop = findLoop(phead);
printList(pLoop);
cout<<“done”<<endl;
return 0;
}



map操作

void mapTest(){
    map testmap;
    //insert key,val in map:
    testmap[1] = true;
    testmap[666] = false;
    //find key in map
    map::iterator it = testmap.find(1);
    if (it != testmap.end()) {
        //key if found in map
        int key = it->first;//this is key
        bool val = it->second;//this is val;
        it->second = !val;
    }
    //delete a key
    testmap.erase(1);
}

CCI题目2-3:Remove Node at Middle of a Link List

两个指针,一个在前面跑,一个跟在后面,前面的跑两步,后面的跑一步。最后删除后面指针指向的那个节点即可。



题目
Implement an algorithm to delete a node in the middle of a single linked list, given only access to that node.
EXAMPLE
Input: the node ‘c’ from the linked list a->b->c->d->e
Result: nothing is returned, but the new linked list looks like a->b->d->e



代码

<

pre>
void RemoveMiddle(Node **ppHead) {
//1,2 del 0; 3,4 del 1; …
if (!(ppHead)) {
return;
}
Node *pRunner = (
ppHead)->next;
Node **ppPre = ppHead;
bool move = false;
while (pRunner) {
pRunner = pRunner->next;
if (move) {
ppPre = &(*ppPre)->next;
}
move = !move;
}
//hold the removing one
pRunner = *ppPre;
//delete it from list
*ppPre = pRunner->next;
//delete it
delete pRunner;
}

int main(int argc, const char * argv[])
{
cout<<“Hello\n”;
string instr;
// instr = “1,2,3,4,5,6,7”;
// instr = “1,2,2,2,2,2,2,1”;
// instr = “1,1,1,1,1,1,1,1,1”;
// instr = “10,9,8,7,6,5,4,3,2,1,0”;
// instr = “0,1,2,3,4,5,6,7,8,9,10”;
instr = “”;
// cin>>instr;
Node *phead = strToList(instr);
printList(phead);
cout<<“process…”<<endl;
RemoveMiddle(&phead);
printList(phead);
cout<<“done”<<endl;
return 0;
}

CCI习题2-2:nTh From the last

画一个链表出来,实际看看就知道怎么写了。
用一个pointer pRun在前面从pHead先跑n个位置。(如果中途为NULL,说明输入的数大于了链表长度)
然后用另一个pointer pCur从pHead开始,和pRun同步往后跑,直到pRun为NULL,这个时候返回pCur就可以了。



题目
Implement an algorithm to find the nth to last element of a singly linked list.



代码,只贴主要部分,用到的其它辅助函数和Node结构参见2-1

<

pre>
//zero based n th from the rear
Node * nThFromLast(Node *pHead, int n) {
if (n < 0) {
cout<<“n below 0″<<endl;
return NULL;
}
Node *pCur = pHead;
Node *pRun = pHead;
//1.let pRun go n position before pCur
for (int i = 0; i <= n; ++i) {
if (!pRun) {
cout<<“Not enough nodes”<<endl;
return NULL;//no enough nodes in the link list
}
pRun = pRun->next;
}
//2.go paralell untile pRun become NULL
while (pRun) {
pRun = pRun->next;
pCur = pCur->next;
}
return pCur;
}
int main(int argc, const char * argv[])
{
cout<<“Hello\n”;
string instr;
// instr = “1,2,3,4,5,6,7”;
// instr = “1,2,2,2,2,2,2,1”;
// instr = “1,1,1,1,1,1,1,1,1”;
instr = “10,9,8,7,6,5,4,3,2,1,0”;
// cin>>instr;
Node *phead = strToList(instr);
printList(phead);
cout<<“process…”<<endl;
Node *pNth = nThFromLast(phead,10);//test 10,9,5,1,0,12,-11
if (pNth) {
cout<value<<endl;
}
cout<<“done”<<endl;
return 0;
}

CCI习题2-1: Remove Duplicates

如果可用缓存的话,可以建一个hashtable,然后track每一个值有没有出现过;
否则的话,只能O(n2)去跑了(见下面代码)



Remove Duplicates
Write code to remove duplicates from an unsorted linked list.
FOLLOW UP
How would you solve this problem if a temporary buffer is not allowed?

<br>
代码

<

pre>
//
// main.cpp
// CCI.2.1.RemoveDuplicate
//
// Created by Qiu Xiangyu on 12-11-14.
// Copyright (c) 2012年 Qiu Xiangyu. All rights reserved.
//

include

include

using namespace std;
struct Node{
int value;
Node *next;
Node(int val):value(val),next(NULL) {;}
};
Node *strToList(string str){
Node *phead = NULL;
Node **ppnext = &phead;
int v = 0;
bool rem = false;
for (int i = 0; i < str.size(); ++i) {
char c = str[i];
if (c >= ‘0’ && c <= ‘9’) {
v = 10 * v + (c – ‘0’);
rem = true;
} else {
*ppnext = new Node(v);
ppnext = &((*ppnext)->next);
v = 0;
rem = false;
}
}
if (rem) {
*ppnext = new Node(v);
}
return phead;
}
void printList(Node *phead) {
cout<<“List : “;
while (phead) {
cout<value;
if (phead->next) {
cout<<“,”;
}
phead = phead->next;
}
cout<<endl;
}

void removeDuplicate(Node *pHead) {
Node *pCur = pHead;
while (pCur) {
Node **ppNext = &pCur->next;
while (*ppNext) {
Node *pNext = *ppNext;
if (pNext->value == pCur->value) {
*ppNext = pNext->next;
delete pNext;
pNext = NULL;
} else {
ppNext = &(*ppNext)->next;
}
}
pCur = pCur->next;
}
}

int main(int argc, const char * argv[])
{
cout<<“Hello\n”;
string instr;
// instr = “1,2,3,4,5,6,7”;
instr = “1,2,2,2,2,2,2,1”;
// instr = “1,1,1,1,1,1,1,1,1”;
// cin>>instr;
Node *phead = strToList(instr);
printList(phead);
cout<<“process…”<<endl;
removeDuplicate(phead);
printList(phead);
cout<<“done”<<endl;
return 0;
}

LeetCode题目:Swap Nodes in Pairs

题目简单,就是每次将两个非空节点swap,然后移动两个位置继续,直到无法找到两个非空节点为止。



Swap Nodes in Pairs
Given a linked list, swap every two adjacent nodes and return its head.
For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.
Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.



代码:16ms过大集合

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *swapPairs(ListNode *head) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        ListNode **ppre = &head;
        
        while(true) {
            ListNode *n0 = *ppre;
            if(NULL == n0) return head;
            ListNode *n1 = n0->next;
            if(NULL == n1) return head;
            
            //swap n0 and n1
            *ppre = n1;
            n0->next = n1->next;
            n1->next = n0;
            ListNode *next = n1->next;
            ppre = &(n0->next);
        }
        
        return head;
    }
};