Блог

пространственная сложность = глубина * потребляемая память. У меня есть журнал глубины (n), поэтому в пространстве сложность равна O (NlogN). В одном блоге medium написано O (N). Поэтому, что правильно?

 class Solution {
public boolean isValidBST(TreeNode root) {
    Queue<TreeNode> nodes = new LinkedList<>();
          depth(root,nodes);
    while(nodes.size()>1){
       TreeNode  node1= nodes.remove();
       TreeNode node2= nodes.element();
        if(node2.val<=node1.val){
            return false;
        }
        
    }
        
        
        
        return true;
}
private void depth(TreeNode root,Queue<TreeNode> nodes){
    if(root==null){
        return;
    }
    depth(root.left,nodes);
    nodes.add(root);
    depth(root.right,nodes);
}
 

}