找到所有不是羅馬的節點，其所有的後代都是羅馬的二叉樹

Question

問題：
設T是二叉樹。定義一個羅馬節點爲T中的一個節點v，這樣v的左子樹中的後代數量最多不超過v的右子樹中的節點數量。描述一個線性時間算法，用於查找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; 
    } 


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

    //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); 
}