JavaScriptを使って二叉樹の基本操作を完成します.

本编は复习の过程で出会った総括のために、面接の准备をしている学生にも参考にしてください.また、紙面が限られているため、本篇の重点は二叉樹のよくあるアルゴリズムと実現にある.
一般的な二叉樹実現コード
前に関連する文章を書きましたが、二叉の木をどのように創建し、遍歴してきたかについては、ここでは詳しく説明しません.関心のある仲間にリンクを提供します.このジャンプをクリックしてください.
フォークを反転
一本の二叉の木に対して、左右の木を反転させると、次の図のようになります.
具体的な実現構想を分析します.

ペアがルートポイントに空きがある場合

この場合は排除が必要です.nullはオブジェクトではないので、左右のツリーが存在しなくて、反転できる場合があります.

本に対して、一本の結点しかない二叉樹

エミリ、この場合も反転できます.この時、根の結点の左右の子樹はnullです.左右の子樹を交換するということは、実は二つのnullを交換しています.理論的には反転しましたが、実際に見たのは反転していない前の結果と同じです.

は、2つ以上の結点を有する1本の二叉樹に対して、二叉樹は、以下のような画像を表すことができる.
左の木だけでも右の木だけでも反転することができます.この言葉は空の子樹と空の子樹を交換することができます.つまり空の子樹に対しては特別な扱いをしません.
分析プロセス
実はこのように私達はやはり二叉樹がどのように反転したのか分かりません.一枚目の二叉樹を例にとって、反転の具体的な過程を見てみます.

まず、根っこの結点を空と判定する必要があります.根の結点が空ではない場合、左右の子樹があります.

本の接合点の左の子樹を左の子樹の根の結点とし、現在のルートの結点については空判定処理を行い、空の場合は左右の子樹を交換しない.

本の结び目の右の子木を右の子木の根の结点として、当面の根の结点に対して空の判定を行って、空の时のために左右の子木を交换しません;

は、ステップ2、3を繰り返し、最後に二叉の木が元の鏡像構造になり、その結果、文章の最初の概略図を参照することができる.

サンプルコード
上記の推理過程によって、次のコードが得られます.

function reverseTree(root){
    if( root !== null){
        [root.left, root.right] = [root.right, root.left]
        reverseTree(root.left)
        reverseTree(root.right)
    }
}

推理の過程は複雑ですが、コードをよく観察してみると、遍歴コードと大差がないようです.出力の結点を交換点に変えます.
二叉の木が完全に対称かどうかを判断します.
一本の左右が完全に対称な二叉の木は、一体どう判断するのですか?

本の結点が空の場合、このときは一本の空の二叉樹で、対称条件(-_-124124124;)

を満たす.

本の結点が一つしかない場合、左右の子樹は全部nullで、左右対称条件を満たす

です.

が2つの結点しかない場合、左右の子樹には必ず1つの空きがあり、対称性がない場合があります.

接合点数は3つ以上の場合、二叉樹は対称的になる可能性があります.

私達の正常な思惟によって、対称かどうかを見て、まず左を見て、それから右を見て、最後に左右が等しいかどうかを比較します.同時に、二叉の木の深さが比較的大きい時には、私たちは左右の光だけでは足りないことに気づきました.左右を比較したら、左と右の右を比較して、左の右と右の左を比較します.
分析プロセス
このように見ると回りくどいです.次に図を見て分析します.

まず根っこの結び目を比較します.子供は

です.

左の子の木の根を結ぶ左の子と右の子の根を結ぶ右の子を比較します.

左の子の木の根を結んでいる右の子と右の子の根を結んでいる左の子を比較します.

上記のプロセスを繰り返します.

サンプルコード

function isSymmetrical(pRoot)
{
    // write code here
    if(!pRoot){
        return true
    }
    return funC(pRoot.left, pRoot.right)
}
 
function funC(left, right){
     
    if(!left){
        return right === null
    }
     
    if(!right){
        return false
    }
     
    if(left.val !== right.val){
        return false
    }
     
    return funC(left.right, right.left) && funC(left.left, right.right)
}

二叉の木の深さを求めます.
分析プロセス

本の接合点が一つしかない場合、二叉樹の深さは1

です.

左サブツリーのみの場合、二叉樹の深さは左サブツリーの深さに1

を加算する.

右サブツリーのみの場合、二叉樹の深さは右サブツリーの深さに1

を加算する.

左右の子樹が同時に存在する場合、二叉樹の深さは左右の子樹の中で最も深いものに1

を加算する.
サンプルコード

function deep(root){
    if(!root){
        return 0
    }
    let left = deep(root.left)
    let right = deep(root.right)
    return left > right ? left + 1 : right + 1
}

二叉の木の幅を求めます.
二叉の木の幅は何ですか?一番多くの接合点を持つ層に含まれる接合点として認識します.例えば、下図のような二叉樹の幅は4です.
分析プロセス
上の図から、私たちはどうやって二叉の幅を計算しますか?実は簡単な考えがあります.

は、第1層の接合点を算出し、

を保存する.

は、第二層の接合点を算出し、一二層における大きな接合点数

を保存する.

以上のプロセスを繰り返す

.
サンプルコード
解析プロセスによれば、このアルゴリズムはキューというデータ構造を利用して実現できます.コードは以下の通りです.

function width(root){
    if(!root){
        return 0
    }
    let queue = [root], max = 1, deep = 1
    while(queue.length){
        while(deep--){
            let temp = queue.shift()
            if(temp.left){
                queue.push(temp.left)
            }
            if(temp.right){
                queue.push(temp.right)
            }
        }
        deep = queue.length
        max = max > deep ? max : deep
    }
    return max
}

二叉の木を再建する
ありふれた遍歴

前シーケンス:

最初にルートを訪問し、左のツリーを巡回して、最後に右のツリーを巡回します.

中序次エルゴード:

最初に左のツリーにアクセスしてルートノードを巡回し、最後に右のツリーを巡回します.

後、順次巡回します.

最初に左の木を遍歴して、右の木を遍歴して、最後にルートノードを訪問します.
テーマの説明
前の順序で巡回して生成されたシーケンスと中の順序で生成されたシーケンスから1つの二叉の木が生成されます.
考え方の分析
もしこの二叉の木があったら、
前の順序は、シーケンスを参照することができます:8 6 5、7、10、11の順に、5、7、8、11の中で、非常に明白な特徴があります.ルートノードの値は、前の順序で、シーケンスの最初の値を遍歴しています.そして、左のサブツリーと右のサブツリーを構成する点で、ルートの接合点の左右の2つのエッジが分かりやすいです.だから、問題を解決する考えが得られます.

は、プリアンブルの最初の値を取得し、ルートノード

を構築する.

は、左のサブツリーのプリアンブルを生成し、シーケンス

を巡回する.

は、右のサブツリーを生成する前の順序で、シーケンス

を巡回する.

上記のプロセスを繰り返します.

サンプルコード

function reConstructBinaryTree(pre, vin)
{
    if(!pre || !vin || !pre.length || !vin.length){
        return null
    }
    let root = new TreeNode(pre[0]),
        tIndex = vin.indexOf(pre[0]),
        leftIn = [],leftPre = [],rightIn = [],rightPre = []
    
    for(let i = 0; i < tIndex; i++){
        leftIn.push(vin[i])
        leftPre.push(pre[i+1])
    }
    for(let i = tIndex+1; i < pre.length; i++){
        rightIn.push(vin[i])
        rightPre.push(pre[i])
    }
    //  
    root.left = reConstructBinaryTree(leftPre, leftIn)
    root.right = reConstructBinaryTree(rightPre, rightIn)
    return root
}

以上の考え、コードが間違っています.コメントエリアで指摘してください.
締め括りをつける
コードの部分は牛客網から来ました.剣の指はofferです.該当するテーマも全部上から見つけられます.
下のQRコードをスキャンしたり、「tony先生の先端塾」を検索したりして、私のWeChatの公衆番号を注目していただければ、最初に私の最新の文章を受け取ることができます.