题解 | #序列化二叉树#

充分利用搜索二叉树的性质，左边永远小于根节点，根节点永远小于右节点进行判断。 那么就会有以下三种情况：

（1）root在p和q中间，那么直接返回root

（2）p和q都小于root，那么利用root的左子树进行递归

（3）以上两种都不是，只能是p和q都在root右边，那么利用root的右子树进行递归

递归的目的是先找到p或q则为共同结点，返回即可

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param p int整型 
     * @param q int整型 
     * @return int整型
     */
    public int lowestCommonAncestor (TreeNode root, int p, int q) {
        // write code here
        return CommonAncestor(root,p,q).val;
    }
    public TreeNode CommonAncestor (TreeNode root, int p, int q) {
        if(p<root.val && root.val<q || q<root.val && root.val<p){
            return root;
        }
        if(p == root.val || q == root.val){
            return root;
        }
        if(p<q && q<root.val){
            return CommonAncestor(root.left,p,q);
        }
        else{
            return CommonAncestor(root.right,p,q);
        }
    }
}