114. Flatten Binary Tree to Linked List

我發現我對tree的遞迴好像特別得心應手

這邊就是可以分成四種case,

左右子樹都存在: 把左子樹拉直後貼到右子樹,再把原本的右子樹往後黏上
左不存在 右存在: 往下拉直右邊
左存在 右不存在: 拉直左邊後往右黏
兩邊皆不存在, 單節點, 直接回傳原本的node即可

要注意在拉直並且黏上的過程, 子樹一定要走到底在黏上去, 否則會蓋掉

class Solution {
public:
  TreeNode *dfs(TreeNode *root) {
    if (!root)
      return nullptr;
if (root->left && root->right) {
      TreeNode *l = dfs(root->left);
      TreeNode *r = dfs(root->right);
root->right = l;
      while(l->right){
          l = l->right;
      }
      l->right = r;
      root->left = nullptr;
} else if (root->left && !root->right) {
      TreeNode *l = dfs(root->left);
      root->right = l;
      root->left = nullptr;
    } else if(!root->left && root->right){
        root->right = dfs(root->right);
}
return root;
  }
void flatten(TreeNode *root) { root = dfs(root); }
};