[LeetCode]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?

这道题是让用非递归的方式中序遍历二叉树。 仿照递归算法执行过程中递归工作站的状态可见： 1. 当栈顶记录中的指针非空时，应遍历左子树，即指向左子树的指针入栈 2. 若栈顶记录中的指针为空，则应退至上一层，若是从左子树返回，则应访问当前栈顶记录中指针所指的根节点 3. 若是从右子树返回，则 表明当前层的遍历结束，应继续退栈。 遍历右子树时不需要保存当前层的根指针，可以直接修改栈顶记录中的指针即可。

下面贴出代码，，有两种形式：

vector<int> inorderTraverse(TreeNode* root){vector<int> ans;stack<TreeNode*> s;s.push(root);TreeNode* p=s.top();while(!s.empty()){while(p){s.push(p->left);p=p->left;}s.pop();//空指针退栈if(!s.empty()){p=s.top();ans.push_back(p->val);s.pop();s.push(p->right);p=p->right;}}return ans;} vector<int> inorderTraverse(TreeNode* root){vector<int> ans;if (root == NULL)return ans;stack<TreeNode*> s;while (root|| !s.empty()){if(root){s.push(root);root=root->left;}else{root=s.top();ans.push_back(root->val);s.pop();root=root->right;}}return ans;}

不做任何解释。没有人明白，