public int lowestCommonAncestor(TreeNode root, int o1, int o2)/记录遍历到的每个节点的父节点/ { Map<Integer, Integer> parent = new HashMap<>(); Queue<TreeNode> queue = new LinkedList<>(); parent.put(root.val, Integer.MIN_VALUE);//给根节点默认一个值 queue.add(root); //直到两个节点都找到为止 while (!parent.containsKey(o1) || !parent.containsKey(o2)) { TreeNode node = queue.poll();//出队 if (node.left != null)//左子节点不为空，记录下他的父节点 { parent.put(node.left.val, node.val); /左子节点不为空，加入队列/ queue.add(node.left); } //右节点 if (node.right != null) { parent.put(node.right.val, node.val); queue.add(node.right); } } Set<Integer> ancestors = new HashSet<>(); //记录下o1和他的祖先节点，从o1节点开始一直到根节点。 while (parent.containsKey(o1)) { ancestors.add(o1); o1 = parent.get(o1); } //查看o1和他的祖先节点是否包含o2节点，如果不包含再看是否包含o2的父节点 while (!ancestors.contains(o2)) o2 = parent.get(o2); return o2;的时间复杂度和空间复杂度是多少

时间复杂度和空间复杂度都是 O(n)，其中 n 为树中节点的数量。

时间复杂度分析：最坏情况下，需要遍历整棵树才能找到两个节点，因此时间复杂度为 O(n)。

空间复杂度分析：需要一个 HashMap 来记录每个节点的父节点，因此空间复杂度为 O(n)。同时需要一个队列来辅助遍历，最大情况下队列中会存储一层所有节点，因此空间复杂度也为 O(n)。两者相加得到总的空间复杂度为 O(n)。

相关问题

#include<iostream>using namespace std;struct TreeNode{ int val; TreeNode* left; TreeNode* right; TreeNode(int v): val(v), left(NULL), right(NULL) {}};TreeNode* buildTree(){ int val; cin >> val; if(val == -1) // 空节点 return NULL; TreeNode* root = new TreeNode(val); root->left = buildTree(); root->right = buildTree(); return root;}void inorderTraversal(TreeNode* root){ if(root == NULL) return; inorderTraversal(root->left); // 中序遍历左子树 cout << root->val << " "; // 输出当前节点 inorderTraversal(root->right); // 中序遍历右子树}int main(){ cout << "请输入二叉树的先序遍历序列（空节点用-1表示）：" << endl; TreeNode* root = buildTree(); cout << "中序遍历结果为：" << endl; inorderTraversal(root); return 0;}用层次遍历搞二叉树

您可以使用以下代码来进行二叉树的层次遍历：

void levelOrder(TreeNode* root) {
    if (!root) {
        return;
    }
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* node = q.front();
        q.pop();
        cout << node->val << " ";
        if (node->left) {
            q.push(node->left);
        }
        if (node->right) {
            q.push(node->right);
        }
    }
}

您只需要在原有的代码中添加以下一行代码即可：

levelOrder(root);

具体来说，您的代码会变成这样：

#include<iostream>
#include<queue>
using namespace std;

struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int v): val(v), left(NULL), right(NULL) {}
};

TreeNode* buildTree(){
    int val;
    cin >> val;
    if(val == -1) // 空节点
        return NULL;
    TreeNode* root = new TreeNode(val);
    root->left = buildTree();
    root->right = buildTree();
    return root;
}

void inorderTraversal(TreeNode* root){
    if(root == NULL)
        return;
    inorderTraversal(root->left);    // 中序遍历左子树
    cout << root->val << " ";        // 输出当前节点
    inorderTraversal(root->right);   // 中序遍历右子树
}

void levelOrder(TreeNode* root) {
    if (!root) {
        return;
    }
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* node = q.front();
        q.pop();
        cout << node->val << " ";
        if (node->left) {
            q.push(node->left);
        }
        if (node->right) {
            q.push(node->right);
        }
    }
}

int main(){
    cout << "请输入二叉树的先序遍历序列（空节点用-1表示）：" << endl;
    TreeNode* root = buildTree();
    cout << "中序遍历结果为：" << endl;
    inorderTraversal(root);
    cout << "\n层次遍历结果为：" << endl;
    levelOrder(root);
    return 0;
}

这样，您的代码就会先进行中序遍历，然后进行层次遍历。

import java.util.ArrayList; import java.util.Arrays; public class Create { public TreeNode CreateTree(int[] preorder,int[] inorder) { if (preorder.length == 0 || inorder.length == 0) { return null; //前序 中序 长度都为0 返回空 } TreeNode root = new TreeNode(preorder[0]);//从前序中获取根节点。 int rootIndex = 0; //获取根节点在中序遍历中的位置 for (int i = 0; i < inorder.length; i++) { if (root.val == inorder[i]) { rootIndex = i; } } int[] Inorderleft = Arrays.copyOfRange(inorder, 0, rootIndex);//把中序遍历从根节点拆开左右两部分 这是左部分 int[] Inorderright = Arrays.copyOfRange(inorder, rootIndex + 1, inorder.length);//把中序遍历从根节点拆开 右部分 int[] Preorderleft= Arrays.copyOfRange(preorder,1,rootIndex);//先序遍历从第一个非根节点的起到根节点在中序中所对应的位置号分为左部分 int[] Preorderright=Arrays.copyOfRange(preorder,rootIndex,preorder.length);//右部分 root.left=CreateTree(Preorderleft,Inorderleft); root.right=CreateTree(Preorderright,Inorderright); return root; } }

您好！您的代码是用于根据前序遍历和中序遍历构建二叉树的函数。这个函数通过递归地构建左子树和右子树来创建整个二叉树。首先，它从前序遍历中获取根节点，然后在中序遍历中找到根节点的索引位置。然后，它将中序遍历拆分为左部分和右部分，并将前序遍历也相应地拆分为左部分和右部分。接下来，它递归地调用自身来构建左子树和右子树，并将其连接到根节点上。最后，它返回根节点。这样就完成了二叉树的构建。

如果您有任何关于这段代码的问题，请随时提问！