/**
 * @author KevinZhu
 * @desc 二叉树中查找指定两个节点的最近公共父节点
 * @date 2021/4/2 12:12
 **/
public class ParentNodeDemo {

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

        // 如果根节点范围下就不包含指定的两个节点
        if (!search(root, num1, num2)) {
            System.out.println("null");
            return;
        }

        do {
            if (search(root.left, num1, num2)) {
            // 左节点中查找到两个子节点，将左节点的作为root继续查找
                root = root.left;
            } else if (search(root.right, num1, num2)) {
                // 右节点中查找到两个子节点，将右节点的作为root继续查找
                root = root.right;
            } else {
                // 左右节点中都没有查找到，则退出查找过程
                break;
            }
        } while (search(root, num1, num2));

        // 此时的root节点，就是查找得到的最小子节点
        System.out.println(root.val);

    }

    /**
     * 判断node节点中是否既包含num1，也包含num2
     */
    private static boolean search(Node node, int num1, int num2) {
        return isOwner(node, num1) && isOwner(node, num2);
    }

    /**
     * 判断node节点中是否包含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;
        }
    }
}