LeetCodeのJavaScriptは98番の解答をします.二叉の検索ツリーを検証します.(Validate Binary Search Tree)

Time:2019/4/24 Title:Vaildaa Binary Search Tree Difficulty:Medium Author:小鹿
テーマ:Vaildaa Binary Search Tree(二叉検索ツリーを検証)
Given a binary tree,determine if it is a valid binary search tree(BST)
Asume a BST is defined as follows:

The left subtree of a node contains only node s with keys less than the node's key.

The right subtree of a node contains only node s with keys greater than the node's key.

Both the left and right subtrees must also be binary search trees.

二叉の木を与えて、有効な二叉検索ツリーかどうかを判断します.
二叉検索ツリーは以下のような特徴があると仮定します.

ノードの左サブツリーは、現在のノードよりも小さい数だけを含む.

ノードの右サブツリーは、現在のノードよりも大きい数だけを含む.

すべての左サブツリーと右サブツリー自体も二叉検索ツリーでなければなりません.

Example 1:

Input:
    2
   / \
  1   3
Output: true

Example 2:

    5
   / \
  1   4
     / \
    3   6
Output: false
Explanation: The input is: [5,1,4,null,null,3,6]. The root node's value
             is 5 but its right child's value is 4.

Solve:
π問題分析
この問題の入手点は、上に提示された3点の捜索樹の3点の要求です.

ノードの左サブツリーは、現在のノードよりも小さい数だけを含む.

ノードの右サブツリーは、現在のノードよりも大きい数だけを含む.

すべての左サブツリーと右サブツリー自体も二叉検索ツリーでなければなりません.

1)以上の3つの点で最も解決しやすいのは、中を巡回して、遍歴した各要素の後の要素が前の要素より大きいかどうかを判断します.条件に合わないなら、2つの検索ツリーではないです.
πアルゴリズムの考え方
1)グローバルのブーメラン変数を定義し、二叉の検索ツリーを返すために使用します.
2)境界値を指定してmax変数を付与します.巡回するごとに、前後のサイズの要件に該当する場合は、現在のノードの値をmax変数に割り当て、次の巡回するノードのサイズの比較に使用します.要求に合わない場合は、そのブール変数をfalseにします.
3)全体の過程は再帰的に解決するものであり、理解においてはやはり常軌を逸している.全体の問題分析の中で一番重要な点です.
πコード実現

var isValidBST = function(root) {
    // boolean   
    let isValidBSTFlag = true;
    //      
    let max = -Number.MAX_VALUE;
    const orderSearch = root => {
        //     （          null）
        if (root) {
            //     
            orderSearch(root.left);
            //               
            if (root.val > max) {
                //        ，       
                max = root.val;
            } else {
                //             ，   false
                isValidBSTFlag = false;
            }
            orderSearch(root.right);
        }
    }
    orderSearch(root);
    return isValidBSTFlag;
};

LeetCodeオープンソースGithub倉庫に一緒に参加することを歓迎します.他の言語のコードを私に提出してもいいです.倉庫の上で堅持して子供達と一緒にカードを打って、共に私達の開源小倉庫を改善します!
Github:https://github.com/luxiangqiang/JS-LeetCode
私の個人番号に注目してください.「平凡に甘んじない私たち」は自分でプログラミングした物語を記録しました.