给定一个二叉树，以集合方式返回其中序/先序方式遍历的所有元素。
有两种方法，一种是经典的中序/先序方式的经典递归方式，另一种可以结合栈来实现非递归
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}". 1 /** 2 * Definition for binary tree 3 * struct TreeNode { 4 * int val; 5 * TreeNode *left; 6 * TreeNode *right; 7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8 * }; 9 */ 10 class Solution { 11 public: 12 vector<int> inorderTraversal(TreeNode *root) { 13 vector<int> ret; 14 if(root == NULL) 15 return ret; 16 17 stack<TreeNode *> stack; 18 stack.push(root); 19 20 while(!stack.empty()){ 21 TreeNode *node = stack.top(); 22 stack.pop(); 23 if(node->left == NULL && node->right == NULL){ 24 ret.push_back(node->val); 25 } 26 else{ 27 if(node->right != NULL) 28 stack.push(node->right); 29 stack.push(node); 30 if(node->left != NULL) 31 stack.push(node->left); 32 33 node->left = node->right = NULL; 34 } 35 36 } 37 38 return ret; 39 40 } 41 };
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].
和上面要求一样，只是要返回以中序方式序列的元素，这次用递归实现：
1 /** 2 * Definition for binary tree 3 * struct TreeNode { 4 * int val; 5 * TreeNode *left; 6 * TreeNode *right; 7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8 * }; 9 */ 10 class Solution { 11 public: 12 vector<int> preorderTraversal(TreeNode *root) { 13 vector<int> ret; 14 if(root == NULL) 15 return ret; 16 PreorderTraversal(root,ret); 17 return ret; 18 } 19 20 void PreorderTraversal(TreeNode *root,vector<int> &ret){ 21 if(root != NULL){ 22 ret.push_back(root->val); 23 PreorderTraversal(root->left,ret); 24 PreorderTraversal(root->right,ret); 25 } 26 } 27 };
转载于:https://www.cnblogs.com/fanchangfa/p/4041649.html
