LeetCode深度優先アルゴリズムのツリー(ツリー変換)

6909 ワード

アルゴリズム-データ構造 dfs ツリー構造 lettecode

以下の5つの練習問題はdfsで配列orチェーンテーブルと二叉木の相互変換の問題を解決し,統一的に一緒に処理することで学習を効果的に強化し,記憶を強固にすることができる.
105.前の順序と中の順序でシーケンスを遍歴して二叉木を構築する
タイトルの説明
1本の木の前順遍歴と中順遍歴に基づいて二叉樹を構築する.
注意:ツリーに重複する要素がないと仮定できます.
たとえば、
プリアンブル遍歴preorder=[3,9,20,15,7]のシーケンス遍歴inorder=[9,3,15,20,7]は、次のツリーを返します.

構想
まずこの問題を解決するには,まず前序と中序遍歴の特徴を知る.前順遍歴の特徴は中左右,すなわち配列の最初の要素であるツリールートノード全体の値であり,中順遍歴の特徴は左中右,すなわち左サブツリーのノードがルートノードの左側,右サブツリーがルートノードの右側である.
上記の特徴によれば,前シーケンス+中シーケンスの遍歴シーケンスに基づいて二叉木を構築することができる.

ツリーのルートノード

は、前のシーケンスのループシーケンスで見つける.

このルートノード

は、中間シーケンスにおいて見出される.
次いで、

は、サブツリー

を再帰的に構築する.
サブツリーを再帰的に構築するには、再帰的ないくつかの条件を明確にする必要があります.

再帰の終了条件

再帰シーケンス構造

まず再帰の終了条件であり,我々はツリーの遍歴結果に基づいてツリーを構築するので,遍歴の配列に基づいて再帰条件を決定することができる.

if (instart == inEnd || preStart == preEnd) return;

次に再帰的な順序構造であり,ルートノードの位置を決定してから対応する左サブツリーと右サブツリーを見つけることができるため,この場合は先にノードを決定してから再帰することであり,先順遍歴と同様である.

ensure the root node;
recursion left;
recursion right;

また,mapを用いて中系列の遍歴結果をキャッシュし,重複遍歴を回避し,空間交換時間を用いることができる.
コード実装

class Solution {
    
    private Map map = new HashMap<>();
    
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        
        int index = 0;
        for (int cur : inorder) {
            map.put(cur, index++);
        }

        return build(preorder, inorder, 0, preorder.length, 0, inorder.length);
    }

    TreeNode build(int[] pre, int[] in, int pStart, int pEnd, int inStart, int inEnd) {
        if (pStart == pEnd) return null;
        
        int rootVal = pre[pStart];
        int rootIndex = map.get(rootVal);

        TreeNode root = new TreeNode(rootVal);
        int leftNum = rootIndex - inStart;

        root.left = build(pre, in, pStart + 1, pStart + 1 + leftNum, inStart, rootIndex);
        root.right = build(pre, in, pStart + 1 + leftNum, pEnd, rootIndex + 1, inEnd);

        return root;

    }
}

106.中間シーケンスと後シーケンスからシーケンスを遍歴して二叉木を構築する
タイトルの説明

                    。

  :
              。

  ，  

     inorder = [9,3,15,20,7]
     postorder = [9,15,7,20,3]
        ：

    3
   / \
  9  20
    /  \
   15   7

構想
この問題は上の105問題とほぼ似ていて、あまり違いはありません.後続のルートノードは、配列の最後の要素です.配列の境界は左開き右閉です.
コード#コード#

class Solution {

    Map map = new HashMap<>();
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        
        int index = 0;
        for (int cur : inorder) {
            map.put(cur, index++);
        }

        return build(inorder, postorder, 0, inorder.length, 0, postorder.length);
    }

    TreeNode build(int[] in, int[] post,int iStart, int iEnd, int pStart, int pEnd) {
        if (iStart == iEnd || pStart == pEnd) return null;

        int rootVal = post[pEnd - 1];
        TreeNode root = new TreeNode(rootVal);

        int rootIndex = map.get(rootVal);
        int leftNum = rootIndex - iStart;

        root.left = build(in, post, iStart, rootIndex, pStart, pStart + leftNum);
        root.right = build(in, post, rootIndex + 1, iEnd, pStart + leftNum, pEnd - 1);

        return root;
    }
}

108.秩序配列を二叉探索ツリーに変換する
タイトルの説明
昇順に配列された秩序配列を、高さバランスツリーに変換します.
本題では,1つの高さバランスツリーとは,1つのツリーの各ノードの左右2つのサブツリーの高さ差の絶対値が1を超えないことを指す.
例:
与えられた秩序配列:[−10,−3,0,5,9],
1つの可能な答えは、[0,-3,9,-10,null,5]であり、次のような高度バランスの二叉探索ツリーを表すことができます.

構想
まず,問題記述に基づいて,この問題は昇順の配列を提供する.二叉探索ツリーの特徴は,中順遍歴が秩序化されていることを知っている.したがって,この問題を二叉探索ツリーにおけるシーケンス遍歴の結果として復元することができる.また,タイトルは高さ差が1を超えない,すなわち左右がバランスしているという条件を与えている.これにより二分探索を用いることができ,midインデックスは実はルートノードに対応する位置であり,midの左側がルートノードの左サブツリーであり,逆に右サブツリーであり,順次再帰すれば本題を解決できる.
コード#コード#

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        if (nums == null || nums.length == 0) return null;

        return build(nums, 0, nums.length - 1);
    }

    TreeNode build(int[] nums, int left, int right) {
        if (left > right) return null;

        int mid = (right - left) / 2 + left;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = build(nums, left, mid - 1);
        root.right = build(nums, mid + 1, right);

        return root;
    }
}

109.秩序チェーンテーブル変換二叉探索ツリー
タイトルの説明
要素が昇順にソートされ、高度にバランスのとれた二叉検索ツリーに変換される単一チェーンテーブルが与えられます.
本題では,1つの高さバランスツリーとは,1つのツリーの各ノードの左右2つのサブツリーの高さ差の絶対値が1を超えないことを指す.
例:
与えられた秩序チェーンテーブル:[−10,−3,0,5,9],
1つの可能な答えは、[0,−3,9,−10,null,5]であり、次のような高度バランスの二叉探索ツリーを表すことができる.

構想
本題は108とほぼ同じで,本題がチェーンテーブルからツリー構造に変換されている点が異なる.チェーンテーブルが中間ノードを計算する方法は配列ほど簡単ではなく,チェーンテーブルは高速ポインタによって実現される.

slow = node;
fast = node;
while (fast.next != boarder && != fast.next.next != null) {
    fast = fast.next.next;
    slow = slow.next;
}

return slow;

チェーンテーブルの中間ノードを計算する方法を知っていれば、二分構造を使用してツリー構造を構築し続けることができます.
コード#コード#

class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) return null;

        return build(head, null);
    }

    TreeNode build(ListNode left, ListNode right) {
        if (left == right) return null;
        ListNode mid = getMid(left, right);
        
        TreeNode root = new TreeNode(mid.val);
        root.left = build(left, mid);
        root.right = build(mid.next, right);

        return root;
    }

    ListNode getMid(ListNode left, ListNode right){
        ListNode slow = left;
        ListNode fast = left;
        
        while (fast.next != right && fast.next.next != right) {
            slow = slow.next;
            fast = fast.next.next;
        }

        return slow;
    }

114.ツリーをチェーンテーブルに展開
タイトルの説明
ツリーを指定し、その場で単一チェーンテーブルに展開します.

構想
展開の順序をよく見ると実際には前順遍歴の順序であるため,まずチェーンテーブルを前順遍歴し,遍歴の結果をリストに格納することができる.
展開するときは順番に関係を作り、左ノードをnullにすればよい.
現在のノードの親ノードは、前のノードの右サブツリーです.
コード#コード#

class Solution {
    
    List list = new ArrayList<>();
    public void flatten(TreeNode root) {
        if (root == null) return ;
        
        pre(root);
        TreeNode pre = null;
        TreeNode cur = null;
        for (int i = 1; i < list.size(); i++) {
            pre = list.get(i - 1);
            cur = list.get(i);

            pre.left = null;
            pre.right = cur;
        }
    }

    void pre(TreeNode root) {
        if (root != null) {
            list.add(root);
            
            pre(root.left);
            pre(root.right);
        }
    }
}

leetcode 7. 逆整数(Reverse Integer)

Flash書き込み後のDSPプログラムの動作が異常な場合の分析