二叉树中两个节点的最近公共祖先

本文主要是介绍二叉树中两个节点的最近公共祖先，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

链接

给定一棵二叉树以及这棵树上的两个节点 o1 和 o2，请找到 o1 和 o2 的最近公共祖先节点。

import java.util.Scanner;


public class Main {

    private static Node solve(Node root, Node h1, Node h2) {
        if (root == null) {
            return null;
        }

        if (h1 == root || h2 == root) {
            return root;
        }

        Node left = solve(root.left, h1, h2);
        Node right = solve(root.right, h1, h2);

        if (left != null && right != null) {
            return root;
        }

        return left == null ? right : left;
    }


    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        while (in.hasNext()) {
            int n = in.nextInt();
            Node[] nodes = new Node[n + 1];
            for (int i = 1; i <= n; ++i) {
                nodes[i] = new Node(i);
            }
            Node root = nodes[in.nextInt()];
            for (int i = 1; i <= n; ++i) {
                int fa = in.nextInt();
                nodes[fa].left = nodes[in.nextInt()];
                nodes[fa].right = nodes[in.nextInt()];
            }
            System.out.println(solve(root, nodes[in.nextInt()], nodes[in.nextInt()]).val);
        }
    }
}

class Node {
    Node left;
    Node right;
    int val;

    public Node(int val) {
        this.val = val;
    }
}

这篇关于二叉树中两个节点的最近公共祖先的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！