一：解题思路
这道题目有2种解法，第一种是递归法，第二种是迭代法。他们的时间复杂度和空间复杂度都为O(n)。
二：完整代码示例 (C++版和Java版)
递归法C++:
class Solution { public: void inorder(TreeNode* root, vector<int>& ret) { if (root != NULL) { inorder(root->left,ret); ret.push_back(root->val); inorder(root->right,ret); } } vector<int> inorderTraversal(TreeNode* root) { vector<int> ret; inorder(root,ret); return ret; } };
递归法Java:
class Solution { public void inorder(TreeNode root,List<Integer> ret) { if(root!=null) { inorder(root.left,ret); ret.add(root.val); inorder(root.right,ret); } } public List<Integer> inorderTraversal(TreeNode root) { List<Integer> ret=new ArrayList<>(); inorder(root,ret); return ret; } }
迭代法C++:
class Solution { public: vector<int> inorderTraversal(TreeNode* root) { vector<int> result; stack<TreeNode*> stack; while (root != NULL || !stack.empty()) { while (root != NULL) { stack.push(root); root = root->left; } TreeNode* s = stack.top(); stack.pop(); result.push_back(s->val); root = s->right; } return result; } };
迭代法Java:
class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> result=new ArrayList<>(); Stack<TreeNode> stack=new Stack<>(); while(root!=null || !stack.isEmpty()) { while(root!=null) { stack.push(root); root=root.left; } TreeNode s=stack.pop(); result.add(s.val); root=s.right; } return result; } }
原文：https://www.cnblogs.com/repinkply/p/12492747.html