本文主要是介绍leetcodeBinary 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? > read more on how binary tree is serialized on OJ.
解题方法
中序遍历二叉树：递归方法：
class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {vector<int> res;if(root==NULL) return res;return inorder(res,root);}vector<int> inorder(vector<int>& res,TreeNode* root){if(root){inorder(res,root->left);res.push_back(root->val);inorder(res,root->right);}return res;}
};迭代方法：
仿照前序遍历使用堆栈，不过是左节点先入栈，直到左孩子为空，出栈，入栈顶元素的右孩子，然后再入右子树的左孩子节点。依次直到堆栈为空，值得注意的是，中序遍历跟先序遍历起始不同的是，根节点不最先入栈！！！代码如下：
class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {vector<int> res;if(root==NULL) return res;stack<TreeNode*> st;TreeNode* node=root;while(!st.empty()||node){if(node){st.push(node);node=node->left;}else{TreeNode* temp=st.top();res.push_back(temp->val);st.pop();node=temp->right;}}return res;}
};这篇关于leetcodeBinary Tree Inorder Traversal的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
