题目描述:
给你两棵二叉树的根节点p和q，编写一个函数来检验这两棵树是否相同。如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的
最简单的方法，就是层序遍历两颗树，比对节点是否为空以及值是否相同。
思路:
1. 每次进两次栈，出二次栈。即分别将两颗树的节点以相同顺序压入栈中。这里用层序遍历，最简单
2. 如果节点都存在而且值一样，那么最终就相等。其他情况就返回不相等即可
3. 稍微重点就是判断节点非空的状态，这里用了一个稍显复杂的或，不过应该很容易理解了
golang示例代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func isSameTree(p *TreeNode, q *TreeNode) bool {
// 用栈，每次出两个
stack := []*TreeNode{p, q}
for len(stack) > 0 {
cur1 := stack[len(stack) - 1]
stack = stack[:len(stack) - 1]
cur2 := stack[len(stack) - 1]
stack = stack[:len(stack) - 1]
if cur1 == nil && cur2 == nil {
continue
}
// 这里判断树的结构是否一样
if (cur1 == nil && cur2 != nil) || (cur1 != nil && cur2 == nil) {
return false
}
// 这里判节点的值是否一样
if cur1.Val != cur2.Val {
return false
}
stack = append(stack, cur1.Left)
stack = append(stack, cur2.Left)
stack = append(stack, cur1.Right)
stack = append(stack, cur2.Right)
}
return true
}
|
不错，内存使用有点高，不过性能还可以
