狗家店面

上来简单自我介绍，然后就开始做题：
Problem statement:
Given a binary tree where some of the nodes need to be removed from the tree. Output the forest (collection of trees) created by removing the nodes indicated by node.shouldBeRemoved == True.
Example:
G

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

curse(leftNode, shouldBeErased(node))
recurse(rightNode, shouldBeErased(node))
if erased and not shouldBeErased(node):
  forest.append(node)
return forest

alli_357 发表于 2020-07-03 11:52:31
是利口 咦以亿令 的小变形

看到题号我一身冷汗：LC已经一亿多题了么

是利口 咦以亿令 的小变形

求大米，谢谢！

    public void delete(TreeNode node， TreeNode parent)    {
        if(node == null)
            return;
        delete(node.left,  node);
        delete(node.right, node);
        if(node.shouldBeRemove)
        {
            if(parent != null)
            {
                if(node == parent.left)
                    parent.left = null;
                else
                    parent.right = null;
            }
        }
        else if(parent == null || parent.shouldBeRemove) // if not to be del, check should be added to the result
        {
            res.add(node);
        }

    }

写了一个work 版本，请指正。


import java.io.*;
import java.util.*;

class TreeNode {
  public char val;
  public TreeNode left;
  public TreeNode right;
  public boolean shouldBeRemove;
  
  public TreeNode (char val, boolean shouldBeRemove) {
    this.val = val;
    this.left = null;
    this.right = null;
    this.shouldBeRemove = shouldBeRemove;
  }
}

class MyCode {
        public static void main (String[] args) {
                TreeNode root = new TreeNode('F', false);
    TreeNode one = new TreeNode('B', true);
    TreeNode two = new TreeNode('G', false);
    root.left = one;
    root.right = two;
    TreeNode three = new TreeNode('A', false);
    TreeNode four = new TreeNode ('D', false);
    one.left = three;
    one.right = four;
    TreeNode five = new TreeNode ('G', false);
    root.right = five;
    TreeNode six = new TreeNode('J', true);
    TreeNode seven = new TreeNode('I', true);
    five.left = six;
    five.right = seven;
    TreeNode eight = new TreeNode('C', false);
    TreeNode nine = new TreeNode('E', false);
    four.left = eight;
    four.right = nine;
    TreeNode ten = new TreeNode('H', false);
    six.left = ten;

    Solution test = new Solution();
    List<TreeNode> res = test.getForest(root);
    for (TreeNode x : res) {
      System.out.println(x.val);
    }
   
        }
}

class Solution {
  
  public List<TreeNode> getForest (TreeNode root) {
   
    List<TreeNode> res = new ArrayList<>();
    if (root == null) return res;
   
    TreeNode node = helper(root, res);
    if (node == root) {
      res.add(root);
    }
    return res;
  }
  
  
  private TreeNode helper(TreeNode root, List<TreeNode> res) {
    if (root == null) return root;
   
    root.left = helper(root.left, res);
    root.right = helper(root.right, res);
   
    if (!root.shouldBeRemove) {
      return root;
    }
   
    if (root.left != null) res.add(root.left); // one forest root;
    if (root.right != null) res.add(root.right);  // one forest root;
    return null;
  }
}