二叉搜索树的最近公共祖先

export function lowestCommonAncestor(root: TreeNode, p: number, q: number): number {
    // write code here
    // 算法思路
    /**
     * 将元素按升序进行排序 获取升序数组
     * 根据二叉搜索树 + 最近公共祖先的特性，最近公共祖先一定在[node(p), node(q)]之间。故此通过P,q获取升序子区间
     * 最后遍历升序子区间[node(p), node(q)] 获取node节点树， 根据dfs算法 判断当前节点能否同时找到 p q 如果能 说明是最近公共祖先
    */
    let array:Array<TreeNode> = []
    inorder(root, array)
    array = getSubArray(array, p, q)

    for(let node of array) {
        if (dfs(node, p) && dfs(node, q)) return node.val
    }
    return root.val
}

// 将元素按升序进行排序
const inorder = (root: TreeNode, array:Array<TreeNode>) => {
    if(root === null) return
    inorder(root.left, array)
    array.push(root)
    inorder(root.right, array)
}
// 锁定查找最近公共祖先的元素区间
const getSubArray = (array:Array<TreeNode>, p: number, q: number) => {
    let left = 0
    let right = array.length - 1
    for(let i = 0 ; i < array.length; i++) {
        if (array[i].val === p) left = i
        if (array[i].val === q) right = i
    }

    return array.splice(left, right)
}
// 通过dfs判断在节点数能否找到目标值
const dfs = (root: TreeNode, target:number) => {
    if(root === null) {
        return false
    } 
    if(root.val === target) {
        return true
    }
    return dfs(root.left, target) || dfs(root.right, target)
}

export function lowestCommonAncestor(root: TreeNode, p: number, q: number): number {
    // write code here
    let cur = root;
    let right;
    let res;
    let next;
    while (cur !== null) {
        if (cur.left !== null) {
            right = cur.left;
            while (right.right !== null && right.right !== cur) {
                right = right.right;
            }
            if (right.right === null) {
                right.right = cur;
                cur = cur.left;
                continue;
            } else {
                right.right = null;
            }
        } 
        //核心代码
        if (cur.val === Math.min(p, q) || cur === next) {
            res = cur;
            if (res === root) return root.val;
            next = cur;
            while (next.right !== null && (next.right.left === null || (next.right.left !== null && next.right.left.val > cur.val))) {
                next = next.right;
            }
            next = next.right;
        }
        if (cur.val === Math.max(p, q)){
            return res.val;
        }
        cur = cur.right;   
    }
}