LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.

---

Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham

• 找到左子树的最右节点，令其右节点指向根节点的右子树

    1
   / \
  2   5
 / \   \
3   4   6

找到左子树的最右节点 4，令其指向 5

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

将根节点的右节点设为左子树，并将左子树置空
1
 \
  2
 / \
3   4
     \
      5
       \
        6

此时根节点的左子树已链接到右子树之上，再以下一个右节点 2 为根节点
找到左子树的最右节点 3，令其指向 4
1
 \
  2
 / \
3 ->4
     \
      5
       \
        6


将 2 的右节点设为左子树，并将左子树置空
1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

再以 3 为根节点，找到左子树的最右节点 3
由于 3 没有左子树，继续右节点，456 同理，最后遍历结束即完成

• 实现如下

class Solution {
 public:
  void flatten(TreeNode* root) {
    while (root) {
      if (root->left) {
        TreeNode* t = getLeftMostRight(root);
        if (t) {
          t->right = root->right;
          root->right = root->left;
          root->left = nullptr;
        }
      }
      root = root->right;
    }
  }

  TreeNode* getLeftMostRight(TreeNode* root) {
    if (!root || !root->left) {
      return nullptr;
    }
    TreeNode* t = root->left;
    while (t->right) {
      t = t->right;
    }
    return t;
  }
};