『剣指offer第2版』面接問題36:二叉木と双方向チェーンテーブル(java)

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

題の要求は順序付けの双方向チェーンテーブルであり、二叉探索木の中序遍歴は各ノードを小さいから大きいまで遍歴するので、中序遍歴と結合することが考えられる.

ツリーは2つのサブノードを指すポインタであり、双方向チェーンテーブルも同様の構造であり、両者の構造は類似しており、ツリーのleftポインタをチェーンテーブルとして前のノードを指すポインタとし、ツリーrightポインタをチェーンテーブルとして後のノードを指すポインタとすることができる.

ツリーのいずれかのノードについて、その前のノードは、その左のサブツリーがソートチェーンテーブルの最後のノードに変換され、その後のノードは、サブツリーからチェーンテーブルに変換された最初のノードである.再帰でできるのは明らかだ.

コード#コード#

   public TreeNode convert(TreeNode root){
       if (root == null) {
           return null;
       }
       // lastListNode            
       TreeNode lastListNode = rConvert(root, null);
       TreeNode headListNode = lastListNode;
       //              
       while (headListNode != null && headListNode.left != null) {
           headListNode = headListNode.left;
       }
       return headListNode;
   }

   /**
    * @param curNode        
    * @param lastListNode              
    * @return            
    */
   TreeNode rConvert(TreeNode curNode, TreeNode lastListNode){
       if (curNode == null) {
           return null;
       }

       if (curNode.left != null) {
           lastListNode = rConvert(curNode.left, lastListNode);
       }
       curNode.left = lastListNode;
       if (lastListNode != null) {
           lastListNode.right = curNode;
       }
       lastListNode = curNode;
       if (curNode.right != null) {
           lastListNode = rConvert(curNode.right, lastListNode);
       }
       return lastListNode;
   }