C*******n
发帖数: 193 | 1 /**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector inorderTraversal(TreeNode *root) {
vector ret;
if(root) {
stack stack;
stack.push(root);
TreeNode* top = stack.top();
while(!stack.empty() || top!=NULL){
while(top->left!=NULL){
stack.push(top->left);
top = top->left;
}
top = stack.top();
ret.push_back(top->val);
stack.pop();
top = top->right;
}
}
return ret;
}
}; |
d********o
发帖数: 15 | 2 好像每回都跳掉了top->right 的node没有入栈 |
y******0
发帖数: 93 | 3 top = top->right;之后top可能为null，然后你上面又继续top->left
【在 C*******n 的大作中提到】
: /**
: * Definition for binary tree
: * struct TreeNode {
: * int val;
: * TreeNode *left;
: * TreeNode *right;
: * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
: * };
: */
: class Solution {
|
f********h
发帖数: 155 | 4 // 不是牛；这样简单
class Solution {
public:
vector inorderTraversal(TreeNode *root) {
vector ret;
stack stack;
TreeNode * top = root;
while (!stack.empty() || top != null) {
if (top != null) {
stack.push(top);
top = top->left;
} else {
top = stack.top();
stack.pop();
ret.push_back(top->val);
top = top->right;
}
}
return ret;
}
}; |
H******7
发帖数: 1728 | 5 good one
★ 发自iPhone App: ChineseWeb 8.7
【在 f********h 的大作中提到】
: // 不是牛；这样简单
: class Solution {
: public:
:
: vector inorderTraversal(TreeNode *root) {
: vector ret;
: stack stack;
: TreeNode * top = root;
: while (!stack.empty() || top != null) {
: if (top != null) {
|
b******g
发帖数: 3616 | 6 基本就是楼上几位说的两个问题
1.top->right始终没有进stack。当第二层的while loop结束后，top访问到了一个没有
left child的节点，输出该节点后访问到了他的right child（top=top->right)，假设
这个节点为X，然后因为stack非空再次回到内层的while loop开始把这个x的left
child依次压入，但x始终没有入栈。
2.如果top->right为NULL，因为stack非空，仍旧会回到内层while loop，此时你直接
访问了NULL->left: while(top->left!=NULL)
【在 C*******n 的大作中提到】
: /**
: * Definition for binary tree
: * struct TreeNode {
: * int val;
: * TreeNode *left;
: * TreeNode *right;
: * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
: * };
: */
: class Solution {
|
