Shulou(Shulou.com)06/01 Report--

This article will explain in detail how to solve the same tree problem in LeetCode. The editor thinks it is very practical, so I share it with you as a reference. I hope you can get something after reading this article.

Topic link

Https://leetcode-cn.com/problems/same-tree/

Topic description

Given two binary trees, write a function to verify that they are the same.

If two trees are structurally identical and the nodes have the same value, they are considered to be the same.

Example 1:

Enter: 1 1

/ /

2 3 2 3

[1,2,3], [1,2,3]

Output: true

Example 2:

Enter: 1 1

/\

2 2

[1,2], [1,null,2]

Output: false

Example 3:

Enter: 1 1

/ /

2 1 1 2

[1,2,1], [1,1,2]

Output: false

The idea of solving the problem

Tags: depth first traversal

Termination condition and return value:

Returns true when the current node of both trees is null

Returns false when one of them is null and the other is not null

Returns false when neither is empty but the values are not equal

Execution process: return when the termination condition is met, and judge whether the left subtree and the right subtree are the same if not, and pay attention to the short-circuit effect in the code.

Time complexity: O (n), n is the number of nodes in the tree

Code

Java version

/ * *

* Definition for a binary tree node.

* public class TreeNode {

* int val

* TreeNode left

* TreeNode right

* TreeNode (int x) {val = x;}

*}

, /

Class Solution {

Public boolean isSameTree (TreeNode p, TreeNode Q) {

If (p = = null & & Q = = null)

Return true

If (p = = null | | Q = = null)

Return false

If (p.val! = q.val)

Return false

Return isSameTree (p.left, q.left) & & isSameTree (p.right, q.right)

}

}

JavaScript version

/ * *

* Definition for a binary tree node.

* function TreeNode (val) {

* this.val = val

* this.left = this.right = null

*}

, /

/ * *

* @ param {TreeNode} p

* @ param {TreeNode} Q

* @ return {boolean}

, /

Var isSameTree = function (p, Q) {

If (p = = null & & Q = = null)

Return true

If (p = = null | | Q = = null)

Return false

If (p.val! = q.val)

Return false

Return isSameTree (p.left, q.left) & & isSameTree (p.right, q.right)

}

Drawing and interpretation

This is the end of this article on "how to solve the same tree problem in LeetCode". I hope the above content can be of some help to you, so that you can learn more knowledge. if you think the article is good, please share it for more people to see.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.