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

1570 ワード

タイトルの説明
ツリーを入力し、ツリーをソートされた双方向チェーンテーブルに変換します.新しいノードを作成できない必要があります.ツリー内のノードポインタの方向を調整するしかありません.
テーマ分析
  • 題の要求は順序付けの双方向チェーンテーブルであり、二叉探索木の中序遍歴は各ノードを小さいから大きいまで遍歴するので、中序遍歴と結合することが考えられる.
  • ツリーは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;
       }