LeetCode | Binary Tree Inorder Traversal

本文主要是介绍LeetCode | 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?

中序遍历，不允许用递归//用递归大家都会写了好吧

这里不能按照上一个那样一点点推进了，上一个可以那样操作是因为左右节点严格按照根-左-右 的顺序，并且是从上到下，不存在任何向回寻找的情况.
所以判断条件node->left就不会被重复判断到。

但是，这个里面访问完了左孩子，还需要对根节点进行访问，这时候这个node->left条件会再次成立，再次将左孩子推入栈中，所以这样会造成死循环的错误。

解决这个错误的办法就是用指针来代替。
即用指针严格控制要去访问哪一个node而不是由弹出的node被动决定。这样就可以得出正确的结果。

stack<TreeNode*> Q;
Q.push(root);
while(!Q.empty()){TreeNode* node=Q.top();if(node->left){Q.push(node->left);continue;}else{result.push_back(node->val);Q.pop();printf("push %d \n",node->val);if(node->right) Q.push(node->right);    }
}

贴上代码，值得详细探究和记忆

class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {vector<int> result;if(root==NULL) return result;stack<TreeNode*> Q;while(root || !Q.empty()){if(root){Q.push(root);root=root->left;}else{root=Q.top();Q.pop();result.push_back(root->val);root=root->right;}}return result;}
};

这篇关于LeetCode | Binary Tree Inorder Traversal的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---