如何在左右方向遍历二叉树

Question

我想要一个解决方案，其中在二进制树中以交替的左右方向遍历。级别顺序遍历为"1 2 3 4 5 6 7"。在需要的条件下，我的输出必须为"1 2 3 7 6 5 4"。下面是我写的代码。这是不对的。

public void traverseLevel(BinaryTreeNode root) {
    Queue<BinaryTreeNode> q = new LinkedList<BinaryTreeNode>();
    q.add(root);
    int c = 0;
    while (!q.isEmpty()) {
        root = q.poll();
        System.out.print(root.getData() + " ");
        if (c == 0) {
            c = 1;
            if (root.getLeft() != null) {
                q.add(root.getLeft());
            }
            if (root.getRight() != null) {
                q.add(root.getRight());
            }
        } else {
            c = 0;
            if (root.getRight() != null) {
                q.add(root.getRight());
            }
            if (root.getLeft() != null) {
                q.add(root.getLeft());
            }
        }
    }
}

我得到的输出是"1 2 3 5 4 6 7">

Answer 1

我从你的问题中了解到，你想按螺旋顺序打印树。

你可以简单地使用两个堆栈

1. 从左到右打印的第一个堆栈
2. 用于从右向左打印的第二堆栈

从根节点开始，您必须将子节点存储在一个堆栈中。因此，对于每个迭代，打印一个堆栈中存在的节点。下一个级别被推送到另一个堆栈中。

Answer 2

我将为您跟踪您的实现。首先，您的队列包含节点1。

1

然后将其子级插入队列中，首先插入左边的子级，因为c为0。

1 2 3

1然后退出队列，所以只剩下

2 3

既然你想从现在开始，3将是理想的起点。然而，2在您的队列中排在第一位，因此它的子项将被推到第一位。

2 3 5 4，然后2退出形成3 5 4

在这一点上，3将把它的子级推到队列中，左边第一个，因为c是0。

3 5 4 6 7

我认为您想要做的是有一个队列和一个堆栈，其中队列包含要打印的项目，堆栈接收从队列中删除的项目。然后，您可以在堆栈中弹出每个项目，并将其子项推入队列。

例如，我们从队列中的1和一个空堆栈开始。然后，我们从队列中删除1，打印它，然后将它推入堆栈。然后我们弹出1，并将其子项首先插入左边的队列中。

2 3

接下来，我们打印2并将其放入堆栈中。与3相同。现在我们的堆栈包含

2 3

然后，我们从堆栈中弹出3，并将它的子项排在第一位。然后我们弹出2并为它的孩子做同样的事情。我们的队列现在包含

7 6 5 4

然后重复这个过程，直到你到达所有的叶子。

另外，一个提示：c可以是布尔值，而不是数字，因为您只使用0和1作为值。这样可以节省空间。：(

Answer 3

以下方法在C++中使用STL

struct TreeNode // basic Tree Structure
{
int data;
TreeNode* leftchild;
TreeNode* rightchild;
}
void alternateLeftRight(TreeNode*root)
{
Stack<TreeNode*>currentLevel; // take two stacks 
Stack<TreeNode*>nextLevel;
currentLevel.push(root);
int LeftToRight=0;  // LeftToRight mean we will approach leftchild before rightchild, if LeftToRight=0 , in this case we will approach rightchild first
while(!currentLevel.empty())
{ 
 TreeNode*temp=currentLevel.top();
 cout<<temp->data<<" ";
 currentLevel.pop();
if(LeftToRight)
{
 if(temp->leftchild)nextLevel.push(leftchild);
 if(temp->rightchild)nextLevel.push(rightchild);
}
else
{
  if(temp->leftchild)nextLevel.push(rightchild);
  if(temp->rightchild)nextLevel.push(leftchild);
}
if(currentLevel.empty())
{
swap(currentLevel,nextLevel);
LeftToRight=1-LeftToRight;
}
}
}