给定一个二叉树，以集合方式返回其中序/先序方式遍历的所有元素。
有两种方法，一种是经典的中序/先序方式的经典递归方式，另一种可以结合栈来实现非递归
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].
OJ's Binary Tree Serialization:
The serialization of a binary tree follows a level order traversal, where '#' signifies a path terminator where no node exists below.
Here's an example:
1
/ \
2 3
/
4
\
5
The above binary tree is serialized as "{1,2,3,#,#,4,#,#,5}".
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> inorderTraversal(TreeNode *root) {
vector<int> ret;
if(root == NULL)
return ret; stack<TreeNode *> stack;
stack.push(root); while(!stack.empty()){
TreeNode *node = stack.top();
stack.pop();
if(node->left == NULL && node->right == NULL){
ret.push_back(node->val);
}
else{
if(node->right != NULL)
stack.push(node->right);
stack.push(node);
if(node->left != NULL)
stack.push(node->left); node->left = node->right = NULL;
} } return ret; }
};
Given a binary tree, return the preorder traversal of its nodes' values.
For example:
Given binary tree {1,#,2,3},
1
\
2
/
3
return [1,2,3].
和上面要求一样，只是要返回以中序方式序列的元素，这次用递归实现：
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> preorderTraversal(TreeNode *root) {
vector<int> ret;
if(root == NULL)
return ret;
PreorderTraversal(root,ret);
return ret;
} void PreorderTraversal(TreeNode *root,vector<int> &ret){
if(root != NULL){
ret.push_back(root->val);
PreorderTraversal(root->left,ret);
PreorderTraversal(root->right,ret);
}
}
};