我想出了這段代碼，但它需要一個全局變量Rank。有什麼辦法可以解決這個問題，而不必擁有一個全局變量？返回二叉樹的序列遍歷的第n項
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 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;
}
或者用MutuableInt從Apache commons lang而不是AtomicInteger。
我不認爲這會正常工作，你在每個函數調用中遞減n。例如，假設樹有10個節點，每個節點都在其父節點的左側。在達到有序遍歷中的第一個節點之前，n將遞減10次。 – Keeto
正確的，它可以被修改爲僅查看是否左/右爲空並且不遞減n（if（node.right == null）rightVal = 0） –
遞歸方法很容易理解，但是如果你的樹形狀違背了期望值，那麼你在這裏最大的棧深度是可以控制的，這可能會限制堆棧內存被一個明確分配的棧結構所消耗。因此，最好花時間建立一個迭代步行者。
首先，定義結構樹節點本身：
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);
}
}
我們會想辦法對事件作出反應期間通過樹的深度，第一次散步信號。從這些方法返回真實意味着訪客希望繼續行走;返回虛假請求，儘快停止步行。
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)
也就是說，有五個節點，其中，數據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指定爲零，因爲它的左子樹已經探索中遇到的第一個節點，一個指定的第二個，依此類推：
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」到控制檯，其在樣品樹前跟蹤步行匹配：第四（即，基於零的上述索引3，每一個參數）發出的「Mid」跡線是用於承載data值爲1的根節點。總而言之，考慮進行足夠的構建，以便將遊戲中的概念形式化，以便您可以在堅實的基礎上更自信地編寫這些特定的查詢。
這沒有意義。你爲什麼要初始化x兩次，y在'int c = x == 0的位置？ Y：X;'？這是關於設計的一個很好的問題。 –
@ArjunPatel在Keeto編輯之前，我從OP複製粘貼代碼（請參閱編輯歷史記錄）。第二個'int x'應該是'int y'。這現在已經修復。 – dasblinkenlight