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
return
Note: Recursive solution is trivial, could you do it iteratively?
解析:二叉木の中序遍歴を求めて、再帰の方法を採用するととても簡単で、もし再帰しないならば、スタックで上層のノードを保存して、左に向かって一番左の葉のノードまで歩いて、それからこの値を出力して、キューの中から弾き出して、右の木が空でないならばこの弾き出したノードの右の子供を押し込んで、スタックが空になるまで上から左に進む手順を繰り返します.
2、Restore IP Addresses
Given a string containing only digits, restore it by returning all possible valid IP address combinations.
For example: Given
return
分析:この問題は私が前に出会った文字列がipアドレスかどうかを判断するのと少し似ています.http://blog.csdn.net/kuaile123/article/details/21600189動的プランニングの手法では、パラメータnumは文字列を何段目、num=4は最後の段を表す、文字列が有効かどうかを直接判断して結果を保存すればよい、そうでなければ0番目、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 inorderTraversal(TreeNode *root) {
vector result;
if(!root){
return result;
}
TreeNode* tempNode = root;
stack 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 restoreIpAddresses(string s) {
vector 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& 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= '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;
}
}
}
};