Leetcode-114. 二叉树展开为链表

发表于 分类于 阅读次数：

题目描述：https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/

解法1：递归

采用后序遍历，对二叉树进行展开操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    void flatten(TreeNode* root) {
        if(root==NULL)
            return;
        flatten(root->left);
        flatten(root->right);
        if(root->left!=NULL)
        {
            auto pre=root->left;
            while(pre->right!=NULL)
            {
                pre=pre->right;
            }
            pre->right=root->right;
            root->right=root->left;
            root->left=NULL;
        }
        return  ;
    }
};

解法2：非递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    void flatten(TreeNode* root) {
          while(root!=NULL)
          {
              if(root->left!=NULL)
              {
                  auto pre=root->left;
                  while(pre->right!=NULL)
                  {
                      pre=pre->right;
                  }
                  pre->right=root->right;
                  root->right=root->left;
                  root->left=NULL;
              }
              //移动根节点
              root=root->right;
          }
    }
};