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

问题

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

例如，给出：

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都顺利通过。