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)。

相关问题

Java遍历子父节点并且获取每个子父节点的长度

可以使用递归的方式遍历Java中的子父节点并获取每个节点的长度，具体实现方式如下：

1. 定义一个方法来遍历节点，方法中需要传入当前节点和当前节点的长度：

public void traverseNode(TreeNode node, int length) {
    // 输出当前节点的长度
    System.out.println("节点 " + node.getName() + " 的长度为：" + length);
    
    // 遍历当前节点的所有子节点
    for (TreeNode child : node.getChildren()) {
        // 递归调用遍历方法，传入子节点和当前节点长度加上子节点的长度
        traverseNode(child, length + child.getLength());
    }
}

2. 在程序中调用该方法，传入根节点和初始长度为0：

TreeNode root = new TreeNode("root", 0);
traverseNode(root, 0);

其中，`TreeNode` 是一个自定义的节点类，包含节点名称和节点长度两个属性，以及一个获取所有子节点的方法 `getChildren()`。在遍历过程中，每次将当前节点的长度加上子节点的长度，就可以得到当前节点的总长度。

#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;}用后序遍历搞二叉树

可以将上述代码中的inorderTraversal函数改为postorderTraversal函数，实现后序遍历输出即可。具体修改如下：

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

然后在主函数中调用postorderTraversal函数即可输出二叉树的后序遍历结果：

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