【每日刷题】二叉树展开为链表

题目地址

https://leetcode-cn.com/problems/path-sum-ii/

题目描述：路径总和II

给定一个二叉树，原地将它展开为链表。

示例：

给定二叉树

   1
  / \
 2   5
/ \   \
3   4   6

将其展开为：

1
\
 2
  \
   3
    \
     4
      \
       5
        \
         6

解答

很简单的一道题，跟着代码走一遍，自然就理解了。

代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void flatten(TreeNode* root) {
        if( !root)  return ;    //终止条件
        TreeNode* temp = root->right;   //暂存右孩子
        root->right = root->left, root->left = NULL;    //将左孩子搬到右孩子处，且随后将左孩子置空
        flatten(temp), flatten(root->right);    //递归处理 暂存的右孩子 和 当前右孩子
        //以下过程为 链接右孩子
        TreeNode* now = root;
        while( now->right)
            now = now->right;
        now->right = temp;
    }
};

当然，递归并不是严格意义上的原地算法。可以使用迭代在严格意义上实现该要求。

迭代：若左侧不为空，则每次将当前结点的右孩子接到当前孩子的左孩子的最右侧。