Java Concise and Easy PreOrder String Based Solution. Linear run time.


  • 0
    M

    Do PreOrder traversal and prepare string for nodes visited. Empty child is represented as "E" .
    Tree
    4
    / \
    1 2
    Appears as _4_1_2_E_E
    Important to append any character ("_" in this case) to separate out the nodes. Without this
    Tree 12 and 2 will end up having incorrect result as "12EE" and "2EE" resulting into incorrect answer when looking for substring 2EE in 12EE.

    public class Solution {
        public boolean isSubtree(TreeNode s, TreeNode t) {
            if(s == null || t == null){return false;}
            StringBuilder sb_s = new StringBuilder(), sb_t = new StringBuilder();
            preOrder(s, sb_s);
            preOrder(t,sb_t);
            return sb_s.toString().contains(sb_t.toString()) ? true: false;
        }
        
        private void preOrder(TreeNode s, StringBuilder sb){
            if(s == null){
                sb.append("_E");
                return;
            }
            sb.append("_").append(s.val);
            preOrder(s.left, sb);
            preOrder(s.right, sb);
        }
    }
    

Log in to reply
 

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