题目

题解

二叉树结构如下：

//Definition for a binary tree node.
    struct TreeNode {
        int val;
        TreeNode *left;
        TreeNode *right;
        TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };

1. 先序递归法

 //本题的顺序可以看出是先序遍历。
class Solution {//两种方法。1、递归法。
public:
    void flatten(TreeNode* root) {
        if(!root) return;//若不存在该节点，直接返回
        if(!root->left && !root->right) return;//若为叶节点，直接返回
        if(root->left) flatten(root->left);
        if(root->right) flatten(root->right);//递归先序遍历
        auto tmp = root->right;//暂存该节点
        root->right = root->left;//将右子树指向其左子树
        root->left = nullptr;//左子树置空
        while(root->right) root = root->right;//然后找到新右子树的最右的节点
        root->right = tmp;//将最右节点接上暂存的原右子树
        return;
    }
};

 1
    / \
   2   5
  / \   \
 3   4   6

     1
    / \
   2   5
    \   \
     3   6
      \    
       4

   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6

2. 非迭代法

//本题的顺序可以看出是先序遍历。
class Solution {//两种方法。2、非迭代法
public:
    void flatten(TreeNode* root) {
        auto cur = root;//设置根节点为当前节点
        while(cur){//若该节点存在就继续遍历
            if(cur->left){//若左子树存在
                auto tmp = cur->left;//暂存左子树
                while(tmp->right) tmp = tmp->right;//找到左子树的最右节点
                tmp->right = cur->right;//接上原右子树
                cur->right = cur->left;//在该节点的右子树加上原左子树
                cur->left = nullptr;//左子树置空
            }
            cur = cur->right;//继续遍历右子树
        }
    }
};

1
    / \
   2   5
  / \   \
 3   4   6

   1
    \
     2
    / \
   3   4
        \
         5
          \
           6
           
   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6

还有应用后序遍历的思想和先序遍历的思想的解法，但是不好理解，先不写了，后续有需要去看题解。