public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null) {
        return null;
    }

    // 如果两个节点值都小于根节点，说明他们都在根节点的左子树上，我们往左子树上找
    if (root.val > p.val && root.val > q.val) {
        return lowestCommonAncestor(root.left, p, q);

        // 如果两个节点值都大于根节点，说明他们都在根节点的右子树上，我们往右子树上找
    } else if (root.val < p.val && root.val < q.val) {
        return lowestCommonAncestor(root.right, p, q);

        // 如果一个节点值大于根节点，一个节点值小于根节点，说明他们他们一个在根节点的左子树上一个在根节点的右子树上，那么根节点就是他们的最近公共祖先节点。
    } else {
        return root;
    }
}

@Test
public void test(){
    System.out.println(lowestCommonAncestor(initTreeNode(), initTreeNode(), initTreeNode()));
}


public TreeNode initTreeNode(){
    TreeNode treeNode1 = new TreeNode(3, null ,null);
    TreeNode treeNode2 = new TreeNode(6, null , null);
    TreeNode treeNode3 = new TreeNode(4, treeNode1, treeNode2);
    TreeNode treeNode4 = new TreeNode(1, null, null);
    TreeNode root = new TreeNode(5, treeNode3, treeNode4);
    return root ;
}

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
    TreeNode(int x, TreeNode left, TreeNode right) {
        this.val = x;
        this.left = left;
        this.right = right;

    }
}