3 5 1 6 2 0 8 null null 7 4
5 1

3

3 5 1 6 2 0 8 null null 7 4
5 4

5

1 2
1 2

1

import sys
from collections import deque

# 定义二叉树的节点类
class TreeNode:
    def __init__(self, x):
        self.val = x          # 节点的值
        self.left = None      # 左子节点
        self.right = None     # 右子节点

# 递归实现寻找两个节点的最近公共祖先
class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        # 如果当前节点为空或者等于 p 或 q，则直接返回当前节点
        if not root or root == p or root == q:
            return root
        # 递归查找左子树和右子树
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        # 如果左右子树均返回非空，则当前节点即为最近公共祖先
        if left and right:
            return root
        # 否则返回不为空的子树
        return left if left else right

# 根据层次遍历构造二叉树，同时保存每个节点的引用，便于查找指定节点
def buildTree(nodes):
    if not nodes or nodes[0] == "null":
        return None, {}
    root = TreeNode(int(nodes[0]))
    mapping = {root.val: root}  # 存储节点值到节点对象的映射
    queue = deque([root])
    i = 1
    while queue and i < len(nodes):
        cur = queue.popleft()
        # 处理左子节点
        if i < len(nodes) and nodes[i] != "null":
            cur.left = TreeNode(int(nodes[i]))
            mapping[cur.left.val] = cur.left
            queue.append(cur.left)
        i += 1
        # 处理右子节点
        if i < len(nodes) and nodes[i] != "null":
            cur.right = TreeNode(int(nodes[i]))
            mapping[cur.right.val] = cur.right
            queue.append(cur.right)
        i += 1
    return root, mapping

if __name__ == "__main__":
    # 读取输入，第一行为层次遍历结果，第二行为两个节点的值
    input_line = sys.stdin.readline().strip()
    node_list = input_line.split()
    second_line = sys.stdin.readline().strip()
    p_val, q_val = map(int, second_line.split())
    
    # 构造二叉树，并获取值到节点的映射
    root, mapping = buildTree(node_list)
    
    # 获取指定的节点对象
    p = mapping.get(p_val, None)
    q = mapping.get(q_val, None)
    
    # 调用算法求解最近公共祖先
    sol = Solution()
    ancestor = sol.lowestCommonAncestor(root, p, q)
    
    # 输出最近公共祖先的值
    if ancestor:
        print(ancestor.val)
    else:
        print("未找到公共祖先")

import java.util.*;

// 定义二叉树节点类
class TreeNode {
    int val;                // 节点的值
    TreeNode left;          // 左子节点
    TreeNode right;         // 右子节点
    TreeNode(int x) { 
        val = x; 
    }
}

class Solution {
    // 递归方法寻找两个节点的最近公共祖先
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 如果当前节点为空或等于 p 或 q，则直接返回
        if (root == null || root == p || root == q)
            return root;
        
        // 递归查找左右子树
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        
        // 如果左右子树均返回非空，则当前节点为最近公共祖先
        if (left != null && right != null)
            return root;
        
        // 否则返回不为空的一侧
        return left != null ? left : right;
    }
}

public class Main {
    // 根据层次遍历构造二叉树，并返回根节点，同时保存节点值与节点对象的映射
    public static TreeNode buildTree(String[] nodes, Map<Integer, TreeNode> mapping) {
        if (nodes.length == 0 || nodes[0].equals("null"))
            return null;
        TreeNode root = new TreeNode(Integer.parseInt(nodes[0]));
        mapping.put(root.val, root);
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int i = 1;
        while (!queue.isEmpty() && i < nodes.length) {
            TreeNode current = queue.poll();
            // 构造左子节点
            if (i < nodes.length && !nodes[i].equals("null")) {
                TreeNode left = new TreeNode(Integer.parseInt(nodes[i]));
                current.left = left;
                mapping.put(left.val, left);
                queue.offer(left);
            }
            i++;
            // 构造右子节点
            if (i < nodes.length && !nodes[i].equals("null")) {
                TreeNode right = new TreeNode(Integer.parseInt(nodes[i]));
                current.right = right;
                mapping.put(right.val, right);
                queue.offer(right);
            }
            i++;
        }
        return root;
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 读取第一行输入，构造树的层次遍历数组
        String line = scanner.nextLine().trim();
        String[] nodes = line.split(" ");
        
        // 读取第二行，两个节点的值
        String secondLine = scanner.nextLine().trim();
        String[] nums = secondLine.split(" ");
        int pVal = Integer.parseInt(nums[0]);
        int qVal = Integer.parseInt(nums[1]);
        
        // 构造二叉树，并保存节点映射关系
        Map<Integer, TreeNode> mapping = new HashMap<>();
        TreeNode root = buildTree(nodes, mapping);
        
        // 获取指定的节点
        TreeNode p = mapping.get(pVal);
        TreeNode q = mapping.get(qVal);
        
        // 调用方法求解最近公共祖先
        Solution sol = new Solution();
        TreeNode ancestor = sol.lowestCommonAncestor(root, p, q);
        
        // 输出最近公共祖先的值
        if (ancestor != null)
            System.out.println(ancestor.val);
        else
            System.out.println("未找到公共祖先");
        
        scanner.close();
    }
}

#include <iostream>
#include <sstream>
#include <queue>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;

// 定义二叉树节点结构体
struct TreeNode {
    int val;                // 节点的值
    TreeNode *left;         // 左子节点
    TreeNode *right;        // 右子节点
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 递归方法寻找最近公共祖先
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    // 如果当前节点为空或等于 p 或 q，则直接返回
    if (root == nullptr || root == p || root == q)
        return root;
    
    // 递归查找左右子树
    TreeNode* left = lowestCommonAncestor(root->left, p, q);
    TreeNode* right = lowestCommonAncestor(root->right, p, q);
    
    // 如果左右子树均返回非空，则当前节点即为最近公共祖先
    if (left != nullptr && right != nullptr)
        return root;
    
    // 否则返回不为空的一侧
    return left != nullptr ? left : right;
}

// 根据层次遍历构造二叉树，同时建立节点值到节点指针的映射
TreeNode* buildTree(const vector<string>& nodes, unordered_map<int, TreeNode*>& mapping) {
    if (nodes.empty() || nodes[0] == "null")
        return nullptr;
    TreeNode* root = new TreeNode(stoi(nodes[0]));
    mapping[root->val] = root;
    queue<TreeNode*> q;
    q.push(root);
    int i = 1;
    while (!q.empty() && i < nodes.size()) {
        TreeNode* curr = q.front();
        q.pop();
        // 构造左子节点
        if (i < nodes.size() && nodes[i] != "null") {
            TreeNode* leftNode = new TreeNode(stoi(nodes[i]));
            curr->left = leftNode;
            mapping[leftNode->val] = leftNode;
            q.push(leftNode);
        }
        i++;
        // 构造右子节点
        if (i < nodes.size() && nodes[i] != "null") {
            TreeNode* rightNode = new TreeNode(stoi(nodes[i]));
            curr->right = rightNode;
            mapping[rightNode->val] = rightNode;
            q.push(rightNode);
        }
        i++;
    }
    return root;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    string line;
    // 读取第一行：层次遍历字符串
    getline(cin, line);
    istringstream iss(line);
    vector<string> nodes;
    string token;
    while (iss >> token) {
        nodes.push_back(token);
    }
    
    // 读取第二行：两个节点的值
    getline(cin, line);
    istringstream iss2(line);
    int pVal, qVal;
    iss2 >> pVal >> qVal;
    
    // 构造二叉树，并建立映射关系
    unordered_map<int, TreeNode*> mapping;
    TreeNode* root = buildTree(nodes, mapping);
    
    // 获取指定的节点指针
    TreeNode* p = mapping[pVal];
    TreeNode* q = mapping[qVal];
    
    // 调用函数求解最近公共祖先
    TreeNode* ancestor = lowestCommonAncestor(root, p, q);
    
    // 输出最近公共祖先的值
    if (ancestor)
        cout << ancestor->val << "\n";
    else
        cout << "未找到公共祖先" << "\n";
    
    return 0;
}