void traverse(TreeNode root) {
     if (root == null) return;
     traverse(root.left);
     // 中序遍歷代碼位置
     print(root.val);
     traverse(root.right);
}

// 解題思路：
// 1. 是否可以通過遍歷一遍二叉樹得到答案？
// 通過中序遍歷可以得到，因?yàn)锽ST的中序遍歷是一個(gè)升序結(jié)果
function isValidBST1(root) {
    let inorder = -Infinity;
    let result = true;
    let traverse = root => {
        if (root === null) {
            return;
        }

        // 前序位置
        traverse(root.left);
        // 中序位置
        // 中序位置獲取當(dāng)前值，并比較其和前一個(gè)值的大小，如果小于等于前一個(gè)值，則證明不是BST樹，則將結(jié)果變?yōu)閒alse
        if (root.val <= inorder) {
            result = false;
        } else {
            inorder = root.val;
        }
        traverse(root.right);
        // 后續(xù)位置
    };

    traverse(root);

    return result;
}

// 將中序遍歷變?yōu)檠h(huán)的方式
function isValidBST2(root) {
    if (root === null) {
        return true;
    }
    let head = root;
    const stack = [];
    let inorder = -Infinity;

    // 中序遍歷的循環(huán)結(jié)構(gòu)是需要?jiǎng)?chuàng)建一個(gè)棧，然后先將左節(jié)點(diǎn)全壓入棧中
    while (stack.length > 0 || head !== null) {
        // 當(dāng)head不為空時(shí)，壓入棧中
        if (head !== null) {
            stack.push(head);
            head = head.left;
        } else {
            // 彈出棧頂元素
            head = stack.pop();
            if (inorder >= head.val) {
                return false;
            }
            inorder = head.val;
            head = head.right;
        }
    }

    return true;
}

// 2. 是否可以定義一個(gè)遞歸函數(shù)，通過子問題（子樹）的答案推導(dǎo)出原問題的答案？
// 答案是可以的,因?yàn)樗阉鞫鏄涞男再|(zhì)是：
// (1)對于BST的每一個(gè)節(jié)點(diǎn)node，左子樹節(jié)點(diǎn)值都比node的值要小，右子樹節(jié)點(diǎn)的值逗比node的值大；
// (2)對于BST的每一個(gè)節(jié)點(diǎn)node，它的左側(cè)子樹和右側(cè)子樹都是BST
// 則我們解決該問題可定義一個(gè)遞歸函數(shù)來進(jìn)行解決

// 注意：該問題需要借助外部變量，因?yàn)楦?jié)點(diǎn)的值必須大于左子樹所有值、小于右子樹所有值，所以需要引入最大最小值

function isValidBST3(root) {
    // 構(gòu)造一個(gè)輔助函數(shù)，判斷根節(jié)點(diǎn)是否在（min，max）范圍內(nèi)
    const helper = (root, min, max) => {
        if (root === null) {
            return true;
        }

        if (root.val <= min) {
            return false;
        }

        if (root.val >= max) {
            return false;
        }

        return helper(root.left, min, root.val) && helper(root.right, root.val, max);
    };

    // 初始狀態(tài)min為-Infinity，max為Infinity
    return helper(root, -Infinity, Infinity);
}

// 對于BST的每一個(gè)節(jié)點(diǎn)node，左子樹節(jié)點(diǎn)的值都比node的值要小，右子樹節(jié)點(diǎn)的值都比node的值大

// 在該問題中，1~n都有可能成為根節(jié)點(diǎn)，然后左邊的是左子樹上的點(diǎn)，右邊的是右子樹上的點(diǎn)，然后對應(yīng)根節(jié)點(diǎn)的搜索樹數(shù)量就是左子樹的組合數(shù) * 右子樹的組合數(shù)；

// 該問題明顯就轉(zhuǎn)換為一個(gè)遞歸問題

function numTree(n) {
    // 為了解決子問題的重復(fù)問題，需要引入備忘錄
    const memo = [];
    for (let i = 0; i < n + 1; i++) {
        memo.push([]);
        for (let j = 0; j < n + 1; j++) {
            memo[i].push(0);
        }
    }
    const count = (low, high) => {
        // 遞歸終止條件
        if (low > high) {
            return 1;
        }

        // 判斷備忘錄中是否存在該值，存在的話直接使用
        if (memo[low][high] > 0) {
            return memo[low][high];
        }
        let result = 0;

        for (let i = low; i <= high; i++) {
            const left = count(low, i - 1);
            const right = count(i + 1, high);

            result += left * right;
        }

        // 將結(jié)果存儲到備忘錄中
        memo[low][high] = result;

        return result;
    };

    return count(1, n);
}

console.log(numTree(3));

// 通過遞歸解決（后續(xù)遍歷）
function lowestCommonAncestor(root, p, q) {
    // 確定遞歸函數(shù)
    const traverse = (node, p, q) => {
        // 確定遞歸終止條件
        if (node === null || node === p || node === q) {
            return node;
        }

        const left = traverse(node.left, p, q);
        const right = traverse(node.right, p, q);

        // 后續(xù)位置
        // 找到一個(gè)節(jié)點(diǎn)，其發(fā)現(xiàn)p、q節(jié)點(diǎn)分別出現(xiàn)在其左右子樹上
        if (left !== null && right !== null) {
            return node;
        }

        // p或q本身就是最近公共祖先
        if (left === null) {
            return right;
        }

        return left;
    };

    return traverse(root, p, q);
}

// 因?yàn)槭嵌嫠阉鳂?，其是有順序的，所以找最近公共祖先?jié)點(diǎn)的問題就轉(zhuǎn)換成了該節(jié)點(diǎn)在[p, q]中間即可
function lowestCommonAncestor(root, p, q) {
    const helper = (node, p, q) => {
        if (node === null) {
            return node;
        }

        if (node.val > p.val && node.val > q.val) {
            const left = helper(node.left, p, q);

            if (left !== null) {
                return left;
            }
        }

        if (node.val < p.val && node.val < q.val) {
            const right = helper(node.right, p, q);
            if (right !== null) {
                return right;
            }
        }

        return node;
    };

    return helper(root, p, q);
}