The same tree

Description: 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 to be the same if they are structurally identical and the nodes have the same value.

See the LeetCode website for an example.

Source: LeetCode Link: https://leetcode-cn.com/probl… Copyright belongs to collar network. Commercial reprint please contact the official authorization, non-commercial reprint please indicate the source.

Solution 1: Recursion

Use the recursive method. The recursive method is as follows:

  • First, return true if p and q are both null;
  • If either p or q is null, false is returned.
  • If p and q are not null, or if p and q are not equal, false is returned. If the values of p and q are equal, then recursively determine whether the left and right subtrees of p and q are equal.

You end the recursion, and you get the result.

public class LeetCode_100 { public static boolean isSameTree(TreeNode p, TreeNode q) { if (p == null && q == null) { return true; } if ((p == null && q ! = null) || (p ! = null && q == null)) { return false; } return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right); } public static void main(String[] args) { TreeNode p = new TreeNode(1); p.left = new TreeNode(2); p.right = new TreeNode(3); TreeNode q = new TreeNode(1); q.left = new TreeNode(2); q.right = new TreeNode(3); System.out.println(isSameTree(p, q)); }}

【 Daily Message 】
Do your best in everything you do, and end up in the right place. Be grateful and content.