首页 > 代码库 > Binary Tree Inorder/Preorder Traversal 返回中序和前序/遍历二叉树的元素集合
Binary Tree Inorder/Preorder Traversal 返回中序和前序/遍历二叉树的元素集合
给定一个二叉树，以集合方式返回其中序/先序方式遍历的所有元素。
有两种方法，一种是经典的中序/先序方式的经典递归方式，另一种可以结合栈来实现非递归
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 5The 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 };
Binary Tree Inorder/Preorder Traversal 返回中序和前序/遍历二叉树的元素集合
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。