2019-06-14.md

每日一题 - flatten-binary-tree-to-linked-list

信息卡片

• 时间：2019-06-14
• 题目链接：https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/
• tag：tree Recursion

题目描述

Given a binary tree, flatten it to a linked list in-place.

For example, given the following tree:

    1
   / \
  2   5
 / \   \
3   4   6
The flattened tree should look like:

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

参考答案

方法1 先序遍历

如果仔细观察输入输出的话会发现，其实输出其实就是输入的先序遍历结果而已。 因此一种做法就是我们对其进行先序遍历，

然后将先序遍历的结果构造成没有左子树的二叉树即可

Time complexity : O(n) Space complexity : O(n)

参考代码

/*
 * @lc app=leetcode id=114 lang=javascript
 *
 * [114] Flatten Binary Tree to Linked List
 */
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
function preorderTraversal(root) {
  if (!root) return [];

  return [root]
    .concat(preorderTraversal(root.left))
    .concat(preorderTraversal(root.right));
}
/**
 * @param {TreeNode} root
 * @return {void} Do not return anything, modify root in-place instead.
 */
var flatten = function(root) {
    if (root === null) return root;
    const res = preorderTraversal(root);
    
    let curPos = 0;
    let curNode = res[0];

    while(curNode = res[curPos]) {
        curNode.left = null;
        curNode.right = res[++curPos];
    }
};

其他优秀解答

方法2 先序遍历优化（递归遍历和非递归遍历）

算法描述

把一颗二叉树变成单链表 flatten(root)

• 递归遍历把一棵树左子树变成单链表 a
• 递归遍历把一棵树右子树变成单链表 b
• 用链表a最后一个元素拼接链表b（递归子问题）

参考代码

• 递归

  
   void flatten(TreeNode* root) {
       if (root == NULL) return ;

       flatten(root->left);
       flatten(root->right);

       //递归子问题
       TreeNode *tmp = root->right;
       root->right = root->left; 
       root->left = NULL;
       
       while (root->right)
       {
         root = root->right; 
       };

        root->right = tmp; 
   }
  };

• 非递归

 
 void flatten(TreeNode* root) {
     if (root == NULL) {
          return ;
     }
     stack<TreeNode*> result;
     result.push(root);
     
     while (!result.empty()){
         TreeNode* cur=result.top();
         result.pop();

         if (cur->right)
         {
            result.push(cur->right);//先顺非递归遍历
         }

         if (cur->left)
         {
            result.push(cur->left);//先顺非递归遍历
         }
         //递归子问题
         if (!result.empty()) 
         {
             cur->right=result.top();
         }
         cur->left=NULL;
     }