[LeetCode 114] - 将树平面化为链表(Flatten Binary Tree to Linked List)

时间:2022-08-21 09:03:53

问题

给出一个二叉树,将其原地平面化为链表。

例如,给出:

1
   /  \
  2    5
 / \     \
3  4     6

平面化后的树看起来应该是这样:

1
 \
  2
    \
     3
       \
        4
          \
           5
             \
              6

初始思路

观察例子中平面化的过程,不难发现其实就是一个二叉树前序遍历的过程。让我们复习一下二叉树前序遍历的方法,根据wiki条目Tree traversal,伪代码如下:

preorder(node)

  if node == null then return
visit(node)
preorder(node.left)
preorder(node.right)
iterativePreorder(node)
parentStack = empty stack
while not parentStack.isEmpty() or node != null
if node != null then
visit(node)
parentStack.push(node.right)
node = node.left
else
node = parentStack.pop()

这里我们实现基本照搬以上伪代码就行了,唯一一点小改动是增加了一个TreeNode*变量来记录前序遍历过程中上一个节点。这样我们在依前序遍历到第n个节点时,可以通过这个指针将第n-1个节点的right指向当前节点,left置空。选择非递归方案的代码如下:

 class Solution {
public:
void flatten(TreeNode *root)
{
if(!root)
{
return;
} previous_ = nullptr; TreeNode* current = root; while(current || !rightCandidates_.empty())
{
if(!current)
{
current = rightCandidates_.top();
rightCandidates_.pop();
} if(previous_)
{
previous_->right = current;
previous_->left = nullptr;
} previous_ = current; if(current->right)
{
rightCandidates_.push(current->right);
} current = current->left;
}
} private: TreeNode* previous_; std::stack<TreeNode*> rightCandidates_;
};

flatten

Judge Small和Judge Large都顺利通过。