Given a binary tree, return the inorder traversal of its nodes‘ values.
Example:
Input: [1,null,2,3] 1 2 / 3 Output: [1,3,2]
Follow up: Recursive solution is trivial, could you do it iteratively?
题目中要求使用迭代用法，利用栈的“先进后出”特性来实现中序遍历。
解法一：（迭代）将根节点压入栈，当其左子树存在时，一直将其左子树压入栈，直至左子树为空，将栈顶元素弹出，将其val值放入vector中，再将其右子树循环上述步骤，直到栈为空。
（C++）
1 vector<int> inorderTraversal(TreeNode* root) { 2 vector<int> m={}; 3 stack<TreeNode*> stack; 4 if(!root) 5 return m; 6 TreeNode* cur=root; 7 while(!stack.empty()||cur){ 8 while(cur){ 9 stack.push(cur); 10 cur=cur->left; 11 } 12 cur=stack.top(); 13 m.push_back(cur->val); 14 stack.pop(); 15 cur=cur->right; 16 } 17 return m; 18 }
方法二：使用递归（C++）
1 void inorder(vector<int> &m,TreeNode* root){ 2 if(root==NULL) 3 return; 4 inorder(m,root->left); 5 m.push_back(root->val); 6 inorder(m,root->right); 7 } 8 9 vector<int> inorderTraversal(TreeNode* root) { 10 vector<int> m={}; 11 if(root==NULL) 12 return m; 13 inorder(m,root); 14 return m; 15 }
LeetCode 94. Binary Tree Inorder Traversal 二叉树的中序遍历 C++
原文：https://www.cnblogs.com/hhhhan1025/p/10658760.html