剣指Offer-26.二叉検索ツリーと双方向チェーンテーブル(Javascript)

26.ツリーと双方向チェーンテーブル
『剣指Offer』ブラシ問題GitHubリンク
タイトルリンク
タイトルの説明
ツリーを入力し、ツリーを並べ替えた双方向チェーンテーブルに変換します.新しいノードを作成できない必要があります.ツリー内のノードポインタの方向を調整するしかありません.
問題を解く構想.

二叉探索木を双方向チェーンテーブルに並べ替えるため,この問題は中順で遍歴すべきであり,木の問題を見ると,基本的に再帰と前中後順で遍歴することが考えられる.

の2つの解題構想は、いずれも再帰に基づいている.

ここで注意したいのは、jsの非基本データ型の伝達問題~エラーが発生する可能性があるため、C++のポインタクラス解法はjsに直接使用できないことです.
Code

解法一:基礎の再帰

左サブツリーを双方向チェーンテーブルとして構築し、チェーンヘッダノードleft

に戻る.

左双方向チェーンテーブルの最後のノード

に位置する.

左双方向チェーンテーブルの最後のノードと現在のノードの双方向リンク

右サブツリーを双方向チェーンテーブルとして構築し、チェーンテーブルヘッダノードright

に戻る.

右双方向チェーンヘッダノードと現在のノードとを

に接続する.

は、双方向チェーンテーブルの一番左のヘッダノード(すなわち、有leftはleft、無leftはルートノードroot)

を返す.

/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */
function Convert(root)
{
    // write code here
    if(!root) return null;
    if(!root.left && !root.right) return root;
    
    //          ，       left
    var left = Convert(root.left);
    var tmp = left;
    
    //      ，  tmp              
    while(tmp && tmp.right){
        tmp = tmp.right;
    }
    //      ，                     
    //    ，tmp left         
    if(tmp){
        tmp.right = root;
        root.left = tmp;
    }
    
    //          ，       right
    var right = Convert(root.right);
    
    //                  
    if(right){
        right.left = root;
        root.right = right;
    }
    
    //     ，              （        ），     ，           
    return left?left:root;
}

解法2:グローバル変数leftLastを用いて左双方向チェーンテーブルの最後のノード(すなわち、前の解法におけるtmp)

を表す.

/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */
var leftLast;
function Convert(root)
{
    // write code here
    if(!root){
        return null;
    }
    //         ，                     
    if(root == null && root == null){
        leftLast = root;
        return root;
    }
    
    //          ，       left
    var left = Convert(root.left);
    
    //      ，                      
    //  ，leftLast left            ！
    if(left){
        leftLast.right = root;
        root.left = leftLast;
    }
    
    //         left，                root 
    leftLast = root;
    
    //          ，       right
    var right = Convert(root.right);
    
    //                  
    if(right){
        right.left = root;
        root.right = right;
    }
    
    //     ，              （        ），     ，           
    return left?left:root;
}