题目:Binary Tree Inorder Traversal
二叉树的中序遍历,和前序、中序一样的处理方式,代码见下:
1 struct TreeNode { 2 int val; 3 TreeNode* left; 4 TreeNode* right; 5 TreeNode(int x): val(x), left(NULL),right(NULL) {} 6 }; 7 8 vector<int> preorderTraversal(TreeNode *root) //非递归的中序遍历(用栈实现) 9 { 10 if (NULL == root) { 11 return vector<int>(); 12 } 13 14 stack<TreeNode *> tree_stack; 15 vector<int> tree_vector; 16 17 TreeNode *pTemp = root; 18 while (pTemp || !tree_stack.empty()) { 19 while (pTemp) { 20 tree_stack.push(pTemp); 21 pTemp = pTemp->left; 22 } 23 if (!tree_stack.empty()) { 24 pTemp = tree_stack.top(); 25 tree_vector.push_back(pTemp->val); 26 tree_stack.pop(); 27 pTemp = pTemp->right; 28 } 29 } 30 return tree_vector; 31 }