在二叉树中查找所有非罗马节点及其所有后代都是罗马节点

Question

问题：
令 T 为二叉树。将罗马节点定义为 T 中的节点 v，使得 v 的左子树中的后代数与 v 的右子树中的节点数最多相差 5。描述用于查找 T 的每个节点 v 的线性时间算法, 使得 v 不是罗马节点，但 v 的所有后代都是罗马节点。

我目前有：
我可以想到 O(n^2)（自上而下的方法）解决方案，我将遍历树并检查节点是否不是罗马节点，然后遍历该节点的后代以检查它们是否都是罗马节点。所以，通过这种方式，我遍历了每个节点两次。
我假设有一种自下而上的方法可以在 O(n) 中找到所需的节点。

有什么想法吗？

Answer 1

谢谢@n.m。征求意见。我已经使用您的输入实施了一个解决方案。
逻辑：
基本逻辑是将节点的 isRoman 字段设置为 false 即使节点的后代（假设孙子）不是罗马人。这意味着即使一个节点满足属性（左右子孙最多为5个）但是如果它的左右子树的isRoman是false，那么当前节点的isRoman 也将是 false。

/*
 * public class TreeNode {
 * int val;
 * int size;        //stores the number of descendants including itself
 * boolean isRoman; // is true when this node is roman and all its descendants are roman, 
 *                  //false even when a grand grand child node of this node is not roman.
 * TreeNode left;
 * TreeNode right;
 * }
 */
public static void roman(TreeNode root, List<TreeNode> lst){
    if(root == null)
        return;
    if(root.left == null && root.right == null){
        root.size = 1;
        root.isRoman = true;
        return;
    }
    int left = 0;
    int right = 0;
    boolean isLeftRoman = false;
    boolean isRightRoman = false;

    if(root.left != null) {
        roman(root.left,lst);
        left = root.left.size;
        isLeftRoman = root.left.isRoman;
    }else{
     isLeftRoman=true;
    }


    if(root.right != null) {
        roman(root.right,lst);
        right = root.right.size;
        isRightRoman = root.right.isRoman;
    }else{
  isRightRoman=true;
        }

    //if the current node is roman and all it's descendants are roman, update isRoman to true
    if(Math.abs(left-right) <= 5 && isLeftRoman && isRightRoman)
        root.isRoman = true;
    else
        root.isRoman = false;

    //update the current node's size
    root.size = left+right+1;

    //add the node to list which is not roman but all its descendants are roman
    if(Math.abs(left-right) > 5 && isLeftRoman && isRightRoman)
        lst.add(root); 
}

在二叉树中查找所有非罗马节点及其所有后代都是罗马节点

Find all nodes which are not Roman and all its descendents are roman in a binary tree

algorithm

tree

binary-tree

binary-search-tree

data-structures