void inorder(TreeNode* root, vector<int>& res) {
时间: 2024-06-01 20:09:41 浏览: 159
&res) {
if(root == NULL) return;
inorder(root -> left, res);
res.push_back(root -> val);
inorder(root -> right, res);
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
inorder(root, res);
return res;
}
相关问题
本题要求实现给定的二叉树的三种遍历。 函数接口定义: void Preorder(BiTree T); void Inorder(BiTree T); void Postorder(BiTree T); T是二叉树树根指针,Preorder、Inorder和Postorder分别输出给定二叉树的先序、中序和后序遍历序列,格式为一个空格跟着一个字符。 其中BinTree结构定义如下: typedef char ElemType; typedef struct BiTNode { ElemType data; struct BiTNode *lchild, *rchild; }BiTNode, *BiTree; 裁判测试程序样例: #include <stdio.h> #include <stdlib.h> typedef char ElemType; typedef struct BiTNode { ElemType data; struct BiTNode *lchild, *rchild; }BiTNode, *BiTree; BiTree Create();/* 细节在此不表 */ void Preorder(BiTree T); void Inorder(BiTree T); void Postorder(BiTree T); int main() { BiTree T = Create(); printf("Preorder:"); Preorder(T); printf("\n"); printf("Inorder:"); Inorder(T); printf("\n"); printf("Postorder:"); Postorder(T); printf("\n"); return 0; } /* 你的代码将被嵌在这里 */ 输入样例: 输入为由字母和'#'组成的字符串,代表二叉树的扩展先序序列。例如对于如下二叉树,输入数据: AB#DF##G##C##
题目描述
给定一个二叉树的先序遍历、中序遍历和后序遍历,请分别输出它们的遍历结果。
样例
输入: AB#DF##G##C##
输出: Preorder: A B D F G C
Inorder: D F G B A C
Postorder: G F D B C A
算法1
(递归) $O(n)$
对于一棵二叉树,有三种基本的遍历方式:
- 先序遍历:从根节点开始,先输出根节点,然后遍历左子树,最后遍历右子树。
- 中序遍历:从根节点开始,先遍历左子树,然后输出根节点,最后遍历右子树。
- 后序遍历:从根节点开始,先遍历左子树,然后遍历右子树,最后输出根节点。
对于一棵二叉树,前序遍历的第一个节点就是这棵树的根节点,而且在中序遍历中,根节点把这个序列分成了左右两个子树的序列,因此可以根据这个性质进行递归求解。假设当前树的前序遍历序列为pre,中序遍历序列为in,那么可以通过查找pre[0]在in中的位置pos,即可确定左右子树的大小,从而分别递归求解左右子树的前序遍历和中序遍历,最后得到整棵树的前序遍历和中序遍历。
后序遍历的求解与前序遍历类似,只不过需要注意递归的顺序。对于一棵树,后序遍历的最后一个节点就是这棵树的根节点,因此可以先递归求解左右子树的后序遍历,再输出根节点。
时间复杂度
对于每个节点,每个节点会被遍历一次,因此时间复杂度为$O(n)$。
C++ 代码
/**
* Definition for a binary tree node.
* 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> res;
if(!root) return res;
stack<TreeNode*> s;
s.push(root);
while(!s.empty()) {
auto node = s.top();
s.pop();
res.push_back(node->val);
if(node->right) s.push(node->right);
if(node->left) s.push(node->left);
}
return res;
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> s;
auto node = root;
while(node || !s.empty()) {
while(node) {
s.push(node);
node = node->left;
}
node = s.top();
s.pop();
res.push_back(node->val);
node = node->right;
}
return res;
}
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
if(!root) return res;
stack<TreeNode*> s1, s2;
s1.push(root);
while(!s1.empty()) {
auto node = s1.top();
s1.pop();
s2.push(node);
if(node->left) s1.push(node->left);
if(node->right) s1.push(node->right);
}
while(!s2.empty()) {
res.push_back(s2.top()->val);
s2.pop();
}
return res;
}
};
给定一个二叉树的根节点 root ,返回 它的中序遍历 。
好的,这是一个二叉树的遍历问题,可以使用递归或迭代的方式来解决。以下是使用递归方式的代码:
```
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
inorder(root, res);
return res;
}
void inorder(TreeNode* root, vector<int>& res) {
if (!root) return;
inorder(root->left, res);
res.push_back(root->val);
inorder(root->right, res);
}
};
```
这段代码可以返回给定二叉树的中序遍历结果。
阅读全文