leetcode

Leetcode submissions
git clone git://git.laack.co/leetcode.git
Log | Files | Refs | README

cousins-in-binary-tree.dart (1401B)

      1 //Given a binary tree return if the nodes with values
      2 //x and y are cousins meaning they are at the same depth
      3 //but do not have the same parent nodes. 
      4 
      5 //To solve this I used DFS to find the depth of the respective nodes, and
      6 //the parent of the target nodes.
      7 //I then compared them to see if they were the same. If they are then they are
      8 //not cousins if they are not then they are.
      9 
     10 //Time: 300ms Beats: 100%
     11 //Memory: 142.9MB Beats: 100%
     12 
     13 class Solution {
     14   bool isCousins(TreeNode? root, int x, int y) {  
     15       CurrNode? x_node = searchForNode(root,x,0,null);
     16       CurrNode? y_node = searchForNode(root,y,0,null);
     17       if(x_node == null || y_node == null){
     18           return false;
     19       }
     20       if(x_node.depth != y_node.depth || x_node.parent == y_node.parent){
     21           return false;
     22       }
     23       return true;
     24 }
     25     CurrNode? searchForNode(TreeNode? root, int target, int depth , TreeNode? parent){
     26         if(root == null){
     27             return null;
     28         }
     29         if(root.val == target){
     30             return CurrNode(parent, depth);
     31         }
     32         CurrNode? left = searchForNode(root.left, target, depth + 1 , root);
     33         CurrNode? right = searchForNode(root.right, target, depth + 1 , root);
     34         if(left != null){
     35             return left;
     36         }
     37         return right;
     38     }
     39 }
     40 class CurrNode{
     41     TreeNode? parent;
     42     int depth;
     43     CurrNode( this.parent, this.depth);
     44 }