Verbose O(n) Java solution using a new Tree with height information


  • 0
    public class Solution {
        
        class HeightNode {
            int val;
            int height;
            HeightNode left;
            HeightNode right;
            HeightNode(int val) {
                this.val = val;
            }
        }
        
        private int computeHeights(HeightNode node) {
            if(node==null)
                return 0;
            node.height = 1+Math.max(computeHeights(node.left), computeHeights(node.right));
            return node.height;
        }
        
        private HeightNode buildHeightNode(TreeNode node) {
            if(node==null)
                return null;
            HeightNode newNode = new HeightNode(node.val);
            newNode.left = buildHeightNode(node.left);
            newNode.right = buildHeightNode(node.right);
            return newNode;
        }
        
        private boolean isSame(HeightNode s, HeightNode t) {
            if(s==null && t==null)
                return true;
            else if(s==null || t==null)
                return false;
            if(s.height != t.height || s.val != t.val)
                return false;
            return isSame(s.left, t.left) && isSame(s.right, t.right);
        }
        
        private boolean helper(HeightNode s, HeightNode t) {
            if(t==null)
                return true;
            if(s==null)
                return false;
            if(s.height < t.height)
                return false;
            else if(s.height == t.height)
                return s.val != t.val ? false : isSame(s, t);
            else
                return helper(s.left, t) || helper(s.right, t);
        }
        
        public boolean isSubtree(TreeNode s, TreeNode t) {
            if(t==null)
                return true;
            HeightNode ss = buildHeightNode(s);
            HeightNode tt = buildHeightNode(t);
            computeHeights(ss);
            computeHeights(tt);
            return helper(ss,tt);
        }
    }

Log in to reply
 

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