Question

Given a binary tree, flatten it to a linked list in-place.

Difficulty:Medium

Category:Tree, Depth-first-Search

Solution

思路是先利用DFS的思路找到最左子节点,然后回到其父节点,把其父节点和右子节点断开,将原左子结点连上父节点的右子节点上,然后再把原右子节点连到新右子节点的右子节点上,然后再回到上一父节点做相同操作。

class Solution {
 public:
  void flatten(TreeNode* root) {
    if (!root) return;
    if (root->left) flatten(root->left);
    if (root->right) flatten(root->right);
    TreeNode* temp = root->right;
    root->right = root->left;
    root->left = nullptr;
    while (root->right) root = root->right;
    root->right = temp;
  }
};
By guozetang            Updated: 2020-09-19 13:02:30

results matching ""

    No results matching ""