剣指offer--26.ツリーと双方向チェーンテーブルの検索

タイトル:ツリーを入力し、ツリーをソートされた双方向チェーンテーブルに変換します.新しいノードを作成できない必要があります.ツリー内のノードポインタの方向を調整するしかありません.
考え方:

左サブツリーを二重チェーンテーブルとして構成する、チェーンテーブルヘッダノード

に戻る.

左サブツリー二重チェーンテーブルの最後のノード

に位置する.

左サブツリーチェーンテーブルが空でない場合は、現在のrootを左サブツリーチェーンテーブル

に追加する.

右サブツリーを二重チェーンテーブルとして構築する、チェーンテーブルヘッダノード

に戻る.

右サブツリーチェーンテーブルが空でない場合、このチェーンテーブルをrootノードの後

に追加する.

は、左サブツリーチェーンテーブルが空であるか否かに基づいて、戻るノード

を決定する.

public class Solution {
public TreeNode Convert(TreeNode root) {
        if(root==null)
            return null;
        if(root.left==null&&root.right==null)
            return root;
        // 1.          ，        
        TreeNode left = Convert(root.left);
        TreeNode p = left;
        // 2.               
        while(p!=null&&p.right!=null){
            p = p.right;
        }
        // 3.            ，   root        
        if(left!=null){
            p.right = root;
            root.left = p;
        }
        // 4.          ，        
        TreeNode right = Convert(root.right);
        // 5.            ，       root    
        if(right!=null){
            right.left = root;
            root.right = right;
        }
        return left!=null?left:root;       
    }
}