1、

Binary Tree Inorder Traversal

Given a binary tree, return the inorder traversal of its nodes' values.

For example:

Given binary tree {1,#,2,3},

   1

    \

     2

    /

   3

return [1,3,2].

Note: Recursive solution is trivial, could you do it iteratively?

分析：求二叉树的中序遍历，採用递归的方法的话很easy，假设非递归的话。就须要用栈来保存上层结点，開始向左走一直走到最左叶子结点，然后将此值输出，从队列中弹出。假设右子树不为空则压入该弹出结点的右孩子，再反复上面往左走的步骤直到栈为空就可以。

class Solution {

public:

    vector<int> inorderTraversal(TreeNode *root) {

        vector<int> result;

        if(!root){

            return result;

        }

        TreeNode* tempNode = root;

        stack<TreeNode*> nodeStack;

        while(tempNode){

            nodeStack.push(tempNode);

            tempNode = tempNode->left;

        }

        while(!nodeStack.empty()){

            tempNode = nodeStack.top();

            nodeStack.pop();

            result.push_back(tempNode->val);

            if(tempNode->right){

                nodeStack.push(tempNode->right);

                tempNode = tempNode->right;

                while(tempNode->left){

                    nodeStack.push(tempNode->left);

                    tempNode = tempNode->left;

                }

            }

        }

        return result;

    }

};

2、Restore IP Addresses

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

For example:

Given "25525511135",

return ["255.255.11.135", "255.255.111.35"].
(Order does not matter)

分析：此题跟我之前遇到的一个推断字符串是否是ip地址有点类似，http://blog.csdn.net/kuaile123/article/details/21600189。採用动态规划的方法，參数num表示字符串表示为第几段。假设num==4则表示最后一段。直接推断字符串是否有效，并保存结果就可以，假设不是则点依次加在第0个、第1个....后面，继续递归推断后面的串。

例如以下：

class Solution {

public:

    vector<string> restoreIpAddresses(string s) {

        vector<string> result;

        int len = s.length();

        if(len < 4 || len > 12){

            return result;

        }

        dfs(s,1,"",result);

        return result;

    }

    void dfs(string s, int num, string ip, vector<string>& result){

        int len = s.length();

        if(num == 4 && isValidNumber(s)){

            ip += s;

            result.push_back(ip);

            return;

        }else if(num <= 3 && num >= 1){

            for(int i=0; i<len-4+num && i<3; ++i){

                string sub = s.substr(0,i+1);

                if(isValidNumber(sub)){

                    dfs(s.substr(i+1),num+1,ip+sub+".",result);

                }

            }

        }

    }

    bool isValidNumber(string s){

        int len = s.length();

        int num = 0;

        for(int i=0; i<len; ++i){

            if(s[i] >= '0' && s[i] <= '9'){

                num = num*10 +s[i]-'0';

            }else{

                return false;

            }

        }

        if(num>255){

            return false;

        }else{

            //非零串首位不为0的推断

            int size = 1;

            while(num = num/10){

                ++size;

            }

            if(size == len){

                return true;

            }else{

                return false;

            }

        }

    }

};