我想出了这段代码，但它需要一个全局变量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)
也就是说，有五个节点，其中数据为 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值一。
总而言之，考虑构建足以形式化正在发挥作用的概念，以便您可以在坚实的基础上更自信地编写这些特定查询。
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;
}
或者使用Apache commons langMutuableInt而不是.AtomicInteger