leetcode114 連鎖表に展開されたバイナリツリー
問題
2分木が与えられたとき、それをその場で1つの連結表に展開する。
例えば、2分木
1
/ \
2 5
/ \ \
3 4 6
と展開する：
1
\
2
\
3
\
4
\
5
\
6
感想
最初は、バイナリツリーを一度トラバースして、新しいリンクテーブルに順番にノードを預けることを考えていました。しかし、書いてみて気づいたのですが、タイトルに「1つのリンクされたテーブルに展開する」とあるので、空間複雑度がO(1)を超えるデータ構造を作ることはできません。
方法1：
最初のアイデアは、バイナリツリーを前の順序でトラバースするためのO(n)スタックを導入しました。
public void flatten(TreeNode root) {
List<TreeNode> result = new LinkedList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode currNode = root;
while(currNode != null ||!stack.isEmpty()) {
while (currNode != null) {
result.add(currNode);
stack.push(currNode);
currNode = currNode.left;
}
currNode = stack.pop();
currNode = currNode.right;
}
for (int i = 1; i < result.size(); i++) {
TreeNode frontNode = result.get(i - 1);
TreeNode curr = result.get(i);
// 1つのリンクされたテーブルになる 左サブツリーはnullになる
frontNode.left = null;
frontNode.right = curr;
}
}
時間の複雑さ：O(n)
空間の複雑さ：O(n)
方法2：
新しいアルゴリズムは、非常に巧妙な方法で定数レベルのパラメーターを使用して実装されていました。問題の解答を読むまでわかりませんでした。下の図を見てください：
ノードの左サブツリーが空の場合、そのノードは1つのリンクされたテーブルの構造に直接適合します。
ノードの左サブツリーが空でない場合、そのノードを1と仮定すると、左サブツリーの最後のノード4は、単一連結表になり、右サブツリーのノード1、5->6は4の下にぶら下がります。だからちょうど左のサブツリーの最後のノードを見つけ、左のサブツリーの最後のノードに右のサブツリーをハングアップすることができますし、ノード1の左のサブツリーがNULLに設定されます。
public void flatten2(TreeNode root) {
while (root != null) {
// ノードの左サブツリーはnullではない
if (root.left != null) {
TreeNode left = root.left;
TreeNode temp = left;
// 左部分木の最後の要素を見つける
while (temp.right != null) {
temp = temp.right;
}
temp.right = root.right;
root.left = null;
root.right = left;
}
// 左サブツリーをヌルにする 現在の点に右サブツリーを直接ぶら下げる
root = root.right;
}
}
時間の複雑さ：O(n)
空間の複雑さ：O(1)
