Tree - 100. Same Tree
100. Same Tree
Given two binary trees, write a function to check if they are the same or not.
Two binary trees are considered the same if they are structurally identical and the nodes have the same value.
Example 1:
Input:
1 1
/ \ / \
2 3 2 3
[1,2,3], [1,2,3]
Output: true思路：
题目很简单，判断两个树是否相同，只要随便使用一种方式遍历一次树就可以，这里使用先序遍历来做。
代码：
go：
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
//recursive
func isSameTree(p *TreeNode, q *TreeNode) bool {
if p == nil && q == nil {
return true
}
if (p == nil && q != nil) || (p != nil && q == nil) {
return false
}
if p.Val != q.Val {
return false
} else {
return isSameTree(p.Left, q.Left) && isSameTree(p.Right, q.Right)
}
}
/* iteratively
func isSameTree(p *TreeNode, q *TreeNode) bool {
if p == nil && q == nil {
return true
}
if (p == nil && q != nil) || (p != nil && q == nil) {
return false
}
stackp := list.New()
stackq := list.New()
stackp.PushBack(p)
stackq.PushBack(q)
for stackp.Len() != 0 || stackq.Len() != 0 {
ep, eq := stackp.Back(), stackq.Back()
stackp.Remove(ep)
stackq.Remove(eq)
curp, curq := ep.Value.(*TreeNode), eq.Value.(*TreeNode)
if curp.Val != curq.Val {
return false
}
if curp.Left != nil && curq.Left != nil{
stackp.PushBack(curp.Left)
stackq.PushBack(curq.Left)
} else if curp.Left == nil && curq.Left == nil {
} else {
return false
}
if curp.Right != nil && curq.Right != nil{
stackp.PushBack(curp.Right)
stackq.PushBack(curq.Right)
} else if curp.Right == nil && curq.Right == nil {
} else {
return false
}
}
return true
}
*/本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019年08月18日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读