Subject to introduce

Force buckle 100 questions: leetcode-cn.com/problems/sa…

Methods a

So the easiest way to think about comparing two binary trees is you have to know what the two binary trees look like, right? So how do you describe what a binary tree looks like? Simple, you can traverse a binary tree using a string representation. The simple code is as follows:

String traverse(TreeNode root) {
    // Empty nodes can be represented by a special character
    if (root == null) {
        return "#";
    }
    // Serialize the left and right subtrees into strings
    String left = traverse(root.left);
    String right = traverse(root.right);
    /* After traversing the code position */
    // Add the left and right subtrees to themselves to serialize the binary tree with itself as root
    String subTree = left + "," + right + "," + root.val;
    return subTree;
}
Copy the code

Therefore, the complete code to change the topic is simple, the complete code is as follows:

public boolean isSameTree(TreeNode p, TreeNode q) {
     return traverse(p).equals(traverse(q));
}

public String traverse(TreeNode root) {
    if(root == null) {
        return "#";
    }
    String left = traverse(root.left);
    String right = traverse(root.right);
    return left+","+right+","+root.val;
}
Copy the code

Complexity analysis

  • Time complexity: O(N)
  • Space complexity: O(N)

Method 2

The space complexity of method 1 is high, so there is no need to use extra space to store traversal results. Two binary trees can be compared while traversing, and the code is as follows:

boolean isSameTree(TreeNode root1, TreeNode root2) {
    // Both are empty, obviously the same
    if (root1 == null && root2 == null) return true;
    // One is null, one is non-null, obviously different
    if (root1 == null || root2 == null) return false;
    // Both are not empty, but val is not the same
    if(root1.val ! = root2.val)return false;

    // Root1 and root2 are all compared
    return isSameTree(root1.left, root2.left)
        && isSameTree(root1.right, root2.right);
}
Copy the code

Complexity analysis

  • Time complexity: O(N)
  • Space complexity: O(H), H is the call depth of the recursive stack, that is, the height of the tree.