“This is the 19th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021”

preface

The same tree as in question 100 is shown below:

Given the root nodes p and q of two binary trees, write a function to check whether the two trees are the same.

Two trees are considered identical if they are structurally identical and the nodes have the same value.

Example 1:

Input: p = [1,2,3], q = [1,2,3] output: trueCopy the code

A, thinking

Two trees are the same:

  • The two trees are structurally identical
  • The corresponding nodes of both numbers have the same value

Obviously, we can use recursion to compare the values of each node in the same direction. As long as there are different situations, it means that the two trees are not the same. Otherwise, the two trees are the same.

Here I use a pre-order traversal (root left and right) to traverse the two trees. We start at the root of P and Q, compare their left children, and finally compare their right children.

Notice, what can happen to a node that means the two nodes are different?

  1. One node is null and the other node is not null
  2. Two non-empty nodes have different values

Except for the above two cases, the nodes are considered equal in all cases, including both empty nodes.

In summary, the general steps are as follows:

  1. Compares whether the current node is the same, if not, returnsfalse
  2. Check whether the left children of the current node are the same, if not, returnfalse
  3. Check whether the right children of the current node are the same, if not, returnfalse

For example

Here p = [1,2,3] and q = [1,2,3] are used as examples

  1. Starting at the root, comparep 和 qThe root node of, obviously1 = = 1, then continue downward
  2. To the left of their children, apparently2 = = 2, then continue downward
  3. More than the left child2Of the left children and children, found both fornull, then backtrack upward
  4. Back to the node1And compare it to the two children on the right3, find the same, continue down
  5. Check with the kid on the right3Of the left children and children, found both fornull
  6. All nodes are equal and the result is returnedtrueCan be

Second, the implementation

The implementation code

The implementation code is consistent with the idea

    public boolean isSameTree(TreeNode p, TreeNode q) {
        return dfs(p, q);
    }

    private boolean dfs(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        } else if (p == null || q == null) {
            return false;
        } else if(p.val ! = q.val) {return false;
        }
        return dfs(p.left, q.left) && dfs(p.right, q.right);
    }
Copy the code

The test code

    public static void main(String[] args) {
        TreeNode p = new TreeNode(1.new TreeNode(2), new TreeNode(3));
        TreeNode q = new TreeNode(1.new TreeNode(2), new TreeNode(3));
        new Number100().isSameTree(p, q);
    }
Copy the code

The results of

Third, summary

Thank you to see the end, very honored to help you ~♥

If you think my writing is good, you might as well give me a thumbs-up! If you have any questions, please see the comments section