PigyChan_LeetCode 1110. 删點成林

1110. 删點成林

難度中等

給出二叉樹的根節點 root，樹上每個節點都有一個不同的值。

如果節點值在 to_delete 中出現，我們就把該節點從樹上删去，最後得到一個森林（一些不相交的樹構成的集合）。

傳回森林中的每棵樹。你可以按任意順序組織答案。

示例：

輸入：root = [1,2,3,4,5,6,7], to_delete = [3,5]

輸出：[[1,2,null,4],[6],[7]]

提示：

(1)樹中的節點數最大為 1000。

(2)每個節點都有一個介于 1 到 1000 之間的值，且各不相同。

(3)to_delete.length <= 1000

(4)to_delete 包含一些從 1 到 1000、各不相同的值。

思路1.0:

在決定删除的節點時，還需要獲得其左右子樹的資訊以生成題目所需要的森林,是以采用後序周遊。

代碼1.0：

class Solution {
  public:
      vector<TreeNode*> rst;


      TreeNode* posOrder(TreeNode* TNode,vector<int>& to_delete)
      {
          if (TNode != NULL)
          {
              TNode->left = posOrder(TNode->left, to_delete);
              TNode->right = posOrder(TNode->right, to_delete);


              for (auto& i : to_delete)
              {
                  if (TNode->val == i)
                  {
                      if(TNode->left!=NULL)
                          rst.push_back(TNode->left);
                      if (TNode->right != NULL)
                          rst.push_back(TNode->right);


                      //在to_delete中删除以找到元素
                      to_delete.erase(remove(to_delete.begin(), to_delete.end(), i), to_delete.end());
                      return NULL;
                  }
              }
              return TNode;
          }
          return TNode;
      }


      vector<TreeNode*> delNodes(TreeNode* root, vector<int>& to_delete) {
          if (root == NULL) return vector<TreeNode*>();
          root = posOrder(root, to_delete);
          if (root != NULL)
          {
              rst.push_back(root);
          }
          return rst;
      }
  };
           

EZ Bro!