Traverse Tree For Once Java Solution


  • 0
    W

    The idea is to convert the tree to a String and compare if one String contains another. The tricky part is to also include "Null" value in the String.
    To do that, first traverse each tree and add all values including null to the list, then, convert those two lists to a String and compare if one String contains another.
    Thanks to @StefanPochmann, there is a bug in my previous post. Cases like [12][2] will fail. The new solution should pass. But this is not a good way to solve problems like this. A formal way would be recursively comparing nodes :)

        public boolean isSubtree(TreeNode s, TreeNode t) {
    		List<Integer> tList = new ArrayList<>();
    		convertToList(t, tList);
    		List<Integer> sList = new ArrayList<>();
    		convertToList(s, sList);
    		String sStr = toString(sList);
    		String tStr = toString(tList);
    		int idx = sStr.indexOf(tStr);
    		return (idx == 0 || (idx >= 2 && sStr.charAt(idx - 2) == ','));
    	}
    
    	private String toString(List<Integer> list) {
    		StringBuilder sb = new StringBuilder();
    		for (int i = 0; i < list.size(); i++) {
    			sb.append(list.get(i)).append(", ");
    		}
    		return sb.toString();
    	}
    
    	private void convertToList(TreeNode node, List<Integer> list) {
    		if (node == null) {
    			list.add(null);
    			return;
    		} else {
    			list.add(node.val);
    			convertToList(node.left, list);
    			convertToList(node.right, list);
    		}
    
    	}
    

  • 0

    Has a bug, doesn't get accepted anymore. (fixed now)


  • 0
    W

    @StefanPochmann Good catch. Fixed now


Log in to reply
 

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