Clear java solution - list comparison upon traversal


  • 0
    public class Solution {
        public boolean isSubtree(TreeNode s, TreeNode t) {
            List<TreeNode> tLikes = new ArrayList<>(); //there maybe multiple nodes that have the same value as t's
            find(s, t, tLikes); 
            if(tLikes.isEmpty()) {
                return false;
            }
            
            List<Integer> tSubtree = new ArrayList<>();
            inOrder(t, tSubtree);
            for(TreeNode tLike : tLikes) {
                List<Integer> tLikeSubtree = new ArrayList<>();
                
                inOrder(tLike, tLikeSubtree);   
                if(tLikeSubtree.equals(tSubtree)) { //2 subtrees are alike if they have the same inOrder traversal
                    return true; 
                }
            }
        
            return false;
        }
        
        private void find(TreeNode s, TreeNode t, List<TreeNode> list) { //return all nodes in s with the same val as t
            if(s == null) {
                return;
            }
            
            if(s.val == t.val) {
                list.add(s);
            }
            
            find(s.left, t, list);
            find(s.right, t, list);
        }
        
        private void inOrder(TreeNode n, List<Integer> list) {
            if(n == null) {
                return;
            }
            inOrder(n.left, list);
            list.add(n.val);
            inOrder(n.right, list);
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.