/**
 * @author KevinZhu
 * @desc 二叉樹中查找指定兩個(gè)節(jié)點(diǎn)的最近公共父節(jié)點(diǎn)
 * @date 2021/4/2 12:12
 **/
public class ParentNodeDemo {

    public static void main(String[] args) {
        Node root = createNode();
        int num1 = 6;
        int num2 = 10;

        // 如果根節(jié)點(diǎn)范圍下就不包含指定的兩個(gè)節(jié)點(diǎn)
        if (!search(root, num1, num2)) {
            System.out.println("null");
            return;
        }

        do {
            if (search(root.left, num1, num2)) {
            // 左節(jié)點(diǎn)中查找到兩個(gè)子節(jié)點(diǎn)，將左節(jié)點(diǎn)的作為root繼續(xù)查找
                root = root.left;
            } else if (search(root.right, num1, num2)) {
                // 右節(jié)點(diǎn)中查找到兩個(gè)子節(jié)點(diǎn)，將右節(jié)點(diǎn)的作為root繼續(xù)查找
                root = root.right;
            } else {
                // 左右節(jié)點(diǎn)中都沒有查找到，則退出查找過程
                break;
            }
        } while (search(root, num1, num2));

        // 此時(shí)的root節(jié)點(diǎn)，就是查找得到的最小子節(jié)點(diǎn)
        System.out.println(root.val);

    }

    /**
     * 判斷node節(jié)點(diǎn)中是否既包含num1，也包含num2
     */
    private static boolean search(Node node, int num1, int num2) {
        return isOwner(node, num1) && isOwner(node, num2);
    }

    /**
     * 判斷node節(jié)點(diǎn)中是否包含num
     */
    private static boolean isOwner(Node node, int num) {
        if (node == null) {
            return false;
        }
        if (node.val == num) {
            return true;
        }
        return isOwner(node.left, num) || isOwner(node.right, num);
    }

    private static Node createNode() {
        Node node8 = new Node(8);
        Node node6 = new Node(6, node8, null);
        Node node7 = new Node(7);
        Node node3 = new Node(3, node6, node7);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node2 = new Node(2, node4, node5);
        Node node1 = new Node(1, node2, node3);
        return node1;
    }

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

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

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