leetcode -day29 Binary Tree Inorder Traversal & Restore IP Addresses

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?

分析:求二叉树的中序遍历,采用递归的方法的话非常简单,如果非递归的话,就需要用栈来保存上层结点,开始向左走一直走到最左叶子结点,然后将此值输出,从队列中弹出,如果右子树不为空则压入该弹出结点的右孩子,再重复上面往左走的步骤直到栈为空即可。

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;
            }
        }
    }
};

leetcode -day29 Binary Tree Inorder Traversal & Restore IP Addresses,布布扣,bubuko.com

时间: 06-14

leetcode -day29 Binary Tree Inorder Traversal & Restore IP Addresses的相关文章

Leetcode 树 Binary Tree Inorder Traversal

本文为senlie原创,转载请保留此地址:http://blog.csdn.net/zhengsenlie Binary Tree Inorder Traversal Total Accepted: 16984 Total Submissions: 48800 Given a binary tree, return the inorder traversal of its nodes' values. For example: Given binary tree {1,#,2,3}, 1 2 /

[LeetCode][JavaScript]Binary Tree Inorder Traversal

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? https://leetcode.

【LeetCode】Binary Tree Inorder Traversal (2 solutions)

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? 解法一:递归 /** * Defi

LeetCode:Binary Tree Inorder Traversal

题目:Binary Tree Inorder Traversal 二叉树的中序遍历,和前序.中序一样的处理方式,代码见下: 1 struct TreeNode { 2 int val; 3 TreeNode* left; 4 TreeNode* right; 5 TreeNode(int x): val(x), left(NULL),right(NULL) {} 6 }; 7 8 vector<int> preorderTraversal(TreeNode *root) //非递归的中序遍历(

LeetCode 94 Binary Tree Inorder Traversal (中序遍历二叉树)

Given a binary tree, return the inorder traversal of its nodes' values. For example: Given binary tree [1,null,2,3], 1 2 / 3 return [1,3,2]. Note: Recursive solution is trivial, could you do it iteratively? 题目链接:https://leetcode.com/problems/binary-t

leetcode No94. Binary Tree Inorder Traversal

Question: Given a binary tree, return the inorder traversal of its nodes' values. For example: Given binary tree [1,null,2,3], 1 2 / 3 return [1,3,2]. Note: Recursive solution is trivial, could you do it iteratively? 中序遍历,左-根-右 Algorithm: 递归,和非递归两种方法

leetcode 94 Binary Tree Inorder Traversal ----- java

Given a binary tree, return the inorder traversal of its nodes' values. For example:Given binary tree [1,null,2,3], 1 2 / 3 return [1,3,2]. Note: Recursive solution is trivial, could you do it iteratively? 求二叉树的中序遍历,要求不是用递归. 先用递归做一下,很简单. /** * Defini

leetCode 94.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? confused what "{1,#,2,3}" means? > rea

LeetCode 94 Binary Tree Inorder Traversal(二叉树的中序遍历)+(二叉树、迭代)

翻译 给定一个二叉树,返回其中序遍历的节点的值. 例如: 给定二叉树为 {1, #, 2, 3} 1 2 / 3 返回 [1, 3, 2] 备注:用递归是微不足道的,你可以用迭代来完成它吗? 原文 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: Recursi