问题

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

例如，给出：

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

[LeetCode 114] - 将树平面化为链表(Flatten Binary Tree to Linked List)的相关教程结束。