このコードを思いついたのですが、グローバル変数が必要ですRank。グローバル変数がなくてもこの問題を解決できる方法はありますか？
int Rank = 0;
public int inOrderTraversal(TreeNode node, int n){
if(node==null)
return 0;
int x=inOrderTraversal(node.left,n);
if(x!=0)return x;
Rank++;
if(n==Rank) return node.data;
int y=inOrderTraversal(node.right,n);
int c= x==0 ? y:x;
return c;
}
二分木の順序通りの走査でn番目の項を返そうとしています。
オブジェクトを再帰呼び出しチェーンに渡し、TraversalStateアクセスしたノードの数を変数に格納できます。
class TraversalState {
public int rank = 0;
}
...
public int inOrderTraversal(TreeNode node, int n, TraversalState ts){
if(node==null)
return 0;
int x=inOrderTraversal(node.left,n, ts);
ts.rank++;
if(n==ts.rank) return node.data;
int y=inOrderTraversal(node.right,n, ts);
int c= x==0 ? y:x;
return c;
}
これで、「グローバル」オブジェクトを使用しないため、実装はスレッドセーフになります。次のように呼び出します。
int r = inOrderTraversal(myNode, targetN, new TraversalState());
再帰的アプローチは理解しやすいですが、ツリーの形状が期待に反する場合は、ここで最大スタック深度に翻弄されます。これにより、明示的に割り当てられたスタック構造によって消費されるヒープメモリがさらに制限される可能性があります。したがって、反復ウォーカーの構築に時間を費やす方がよいでしょう。
まず、ツリーノード自体の構造を定義します。
public final class TreeNode {
public final int data;
public final TreeNode left, right;
public TreeNode(int data, TreeNode left, TreeNode right) {
this.data = data;
this.left = left;
this.right = right;
}
public TreeNode(int data) {
this(data, null, null);
}
}
深さ優先探索中に通知されたイベントに反応する方法が必要です。これらのメソッドからtrueを返すことは、訪問者が散歩の継続を望んでいることを示します。ウォークができるだけ早く停止するという誤った要求を返します。
public abstract class Visitor {
public boolean visitPre(TreeNode node) {
return true;
}
public boolean visitMid(TreeNode node) {
return true;
}
public boolean visitPost(TreeNode node) {
return true;
}
}
ここで、反復インオーダーウォークアルゴリズムを定義します。
final class InOrder {
private InOrder() {}
private static final class Breadcrumb {
public final TreeNode node;
public final boolean rightIsNext; // Not a great name.
public Breadcrumb(TreeNode node, boolean rightIsNext) {
this.node = node;
this.rightIsNext = rightIsNext;
}
public static Breadcrumb goingLeft(TreeNode departingPoint) {
return new Breadcrumb(departingPoint, true);
}
public static Breadcrumb goingRight(TreeNode departingPoint) {
return new Breadcrumb(departingPoint, false);
}
}
public static <T extends Visitor> T walk(TreeNode root, T visitor) {
if (null == root ||
null == visitor)
throw new NullPointerException();
final Deque<Breadcrumb> stack = new ArrayDeque<Breadcrumb>();
if (!visitor.visitPre(root))
return visitor;
for (;;) {
for (TreeNode left = root.left;
null != left;
root = left, left = root.left) {
if (!visitor.visitPre(left))
return visitor;
stack.push(Breadcrumb.goingLeft(root));
}
if (!visitor.visitMid(root))
return visitor;
final TreeNode right = root.right;
if (null != right) {
if (!visitor.visitPre(right))
return visitor;
stack.push(Breadcrumb.goingRight(root));
root = right;
} else {
if (!visitor.visitPost(root))
return visitor;
// Go back up the tree until we find a node with an unexplored right child.
for (;;) {
if (stack.isEmpty())
return visitor;
final Breadcrumb breadcrumb = stack.pop();
if (breadcrumb.rightIsNext) {
if (!visitor.visitMid(breadcrumb.node)) {
return visitor;
}
if (null != breadcrumb.node.right) {
if (!visitor.visitPre(breadcrumb.node.right))
return visitor;
stack.push(Breadcrumb.goingRight(breadcrumb.node));
root = breadcrumb.node.right;
break;
}
}
if (!visitor.visitPost(breadcrumb.node))
return visitor;
}
}
}
}
}
サンプルツリーでwalk()関数を実行します。
(1)
|
+-+-+
| |
(2) (5)
|
+-+-+
| |
(3) -
|
+-+-+
| |
- (4)
つまり、5つのノードがあり、データ4と5の両方の葉が正しい子です。
final TreeNode root = new TreeNode(1,
new TreeNode(2,
new TreeNode(3,
null,
new TreeNode(4)),
null),
new TreeNode(5));
walk(root,
new Visitor() {
private final PrintStream ps = System.out;
@Override
public boolean visitPre(TreeNode node) {
trace(node, "Pre");
return true;
}
@Override
public boolean visitMid(TreeNode node) {
trace(node, "Mid");
return true;
}
@Override
public boolean visitPost(TreeNode node) {
trace(node, "Post");
return true;
}
private TreeNode trace(TreeNode node, String phase) {
ps.print(phase);
ps.print('(');
ps.print(node.data);
ps.println(')');
return node;
}
});
これにより、次のように出力されます。
Pre(1)
Pre(2)
Pre(3)
Mid(3)
Pre(4)
Mid(4)
Post(4)
Post(3)
Mid(2)
Post(2)
Mid(1)
Pre(5)
Mid(5)
Post(5)
Post(1)
ここで、順序どおりの歩行中に遭遇したn番目のノードを見つけるための便利な方法を求めました。と呼ばれる関数を記述しますfindNthInOrder()。ここで、パラメーターnは、左側のサブツリーが既に探索されている最初のノードとしてゼロを指定し、1つは2番目のノードを指定します。
private static TreeNode findNthInOrder(TreeNode root, final int n) {
if (n < 0)
throw new IllegalArgumentException();
return walk(root,
new Visitor() {
public TreeNode found = null;
private int remaining = n + 1;
@Override
public boolean visitMid(TreeNode node) {
if (0 == --remaining) {
found = node;
return false;
}
return true;
}
}).found;
}
サンプルツリーでこの関数を呼び出すと、期待される結果が得られます。
final TreeNode nth = findNthInOrder(root, 3);
System.out.println(null != nth ? nth.data : "(none)");
これにより、コンソールに「1」が出力されます。これは、サンプルツリー上の前のトレースウォークと一致します。4番目（つまり、上記の引数によるゼロベースのインデックス3）の「Mid」トレースは、data1の値。
要約すると、これらの特定のクエリを健全な基盤の上に自信を持って書くことができるように、実際の概念を形式化するのに十分なものを構築することを検討してください。
public int inOrderTraversal(TreeNode node, AtomicInteger n){
if(node == null) return 0;
if(n == 0) return node.data;
int leftVal = inOrderTraversal(node.left, n.decrementAndGet());
if(n == 0) return node.data;
int rightVal = inOrderTraversal(node.right,n.decrementAndGet());
return leftVal == 0 ? rightVal : leftVal;
}
または、の代わりにApachecommonslangMutuableIntから使用します。AtomicInteger