给定一个以1为根的树，输出树的中序遍历

对于一棵以1为根的树，中序遍历的顺序为：

1. 先遍历1的左子树
2. 输出1
3. 再遍历1的右子树

具体实现可以使用递归的方式，先递归遍历左子树，再输出当前节点，最后递归遍历右子树。代码如下：

void inorderTraversal(int cur, vector<int>& res, vector<vector<int>>& tree) {
    if (cur == -1) return; // 如果当前节点为空，直接返回
    inorderTraversal(tree[cur][], res, tree); // 遍历左子树
    res.push_back(cur); // 输出当前节点
    inorderTraversal(tree[cur][1], res, tree); // 遍历右子树
}

vector<int> inorderTraversal(vector<vector<int>>& tree) {
    vector<int> res;
    inorderTraversal(1, res, tree); // 从根节点1开始遍历
    return res;
}

相关问题

给定一棵满二叉树树先序遍历的输出结果，求该树中序遍历的输出结果。

对于一棵满二叉树，其中序遍历的输出结果可以通过以下步骤得到：

1. 将树先序遍历结果分为三个部分：根节点、左子树的先序遍历结果、右子树的先序遍历结果。

2. 递归处理左子树的先序遍历结果，得到该子树的中序遍历结果。

3. 递归处理右子树的先序遍历结果，得到该子树的中序遍历结果。

4. 将根节点的值插入到左子树的中序遍历结果的末尾。

5. 将右子树的中序遍历结果插入到上一步得到的结果的末尾。

6. 返回最终的中序遍历结果。

具体实现可以参考以下代码（假设输入的树先序遍历结果已经存储在一个数组 pre 中）：

vector<int> inorder(int l, int r) {
    if (l > r) return {};
    if (l == r) return {pre[l]};
    int mid = l + (r - l + 1) / 2;
    auto left = inorder(l + 1, mid);
    auto right = inorder(mid + 1, r);
    left.push_back(pre[l]);
    left.insert(left.end(), right.begin(), right.end());
    return left;
}

其中，函数 inorder(l, r) 表示处理 pre[l] 到 pre[r] 这段区间的先序遍历结果，返回对应的中序遍历结果。在函数中，首先处理边界情况，即当 l > r 或者 l == r 时，直接返回对应的结果。否则，找到当前区间的中间位置 mid，然后分别递归处理左右子树的先序遍历结果，得到对应的中序遍历结果 left 和 right。将根节点的值 pre[l] 插入到 left 的末尾，然后将 right 的结果插入到 left 的末尾，最后返回 left 即可。

给定二叉树的后序遍历和中序遍历，输出前序遍历

根据给定的后序遍历和中序遍历，可以构造出二叉树，然后再进行前序遍历输出。具体步骤如下：

1.定义一个TreeNode类，包含val、left、right三个属性，用于表示二叉树的节点。

2.定义一个函数buildTree，接收两个参数inorder和postorder，分别表示中序遍历和后序遍历。

3.在buildTree函数中，首先判断inorder和postorder是否为空，如果为空，则返回None。

4.然后从postorder中取出最后一个元素，作为当前子树的根节点。

5.在inorder中找到根节点的位置，将inorder分成左子树和右子树两部分。

6.递归调用buildTree函数，分别传入左子树的中序遍历和后序遍历，以及右子树的中序遍历和后序遍历，得到左子树和右子树的根节点。

7.将左子树和右子树的根节点分别作为当前根节点的左右子节点。

8.最后返回当前根节点。

9.定义一个函数preorderTraversal，接收一个参数root，表示二叉树的根节点。

10.在preorderTraversal函数中，首先判断root是否为空，如果为空，则返回空列表。

11.然后按照根节点、左子树、右子树的顺序进行前序遍历，将遍历结果存入列表中。

12.最后返回列表。

下面是完整的代码实现：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def buildTree(inorder, postorder):
    if not inorder or not postorder:
        return None
    root_val = postorder[-1]
    root = TreeNode(root_val)
    index = inorder.index(root_val)
    left_inorder = inorder[:index]
    right_inorder = inorder[index+1:]
    left_postorder = postorder[:index]
    right_postorder = postorder[index:-1]
    root.left = buildTree(left_inorder, left_postorder)
    root.right = buildTree(right_inorder, right_postorder)
    return root

def preorderTraversal(root):
    if not root:
        return []
    res = [root.val]
    res += preorderTraversal(root.left)
    res += preorderTraversal(root.right)
    return res

inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3]
root = buildTree(inorder, postorder)
print(preorderTraversal(root)) # 输出：[3, 9, 20, 15, 7]