
问题
给定两个二叉树,编写一个函数来检验它们是否相同。
如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。
输入: 1 1
/ \ / \
2 3 2 3[1,2,3], [1,2,3]
输出: true
输入: 1 1
/ \
2 2[1,2], [1,null,2]
输出: false
输入: 1 1
/ \ / \
2 1 1 2[1,2,1], [1,1,2]
输出: false
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.
Input: 1 1
/ \ / \
2 3 2 3[1,2,3], [1,2,3]
Output: true
Input: 1 1
/ \
2 2[1,2], [1,null,2]
Output: false
Input: 1 1
/ \ / \
2 1 1 2[1,2,1], [1,1,2]
Output: false
示例
public class Program { public static void Main(string[] args) { var p = new TreeNode(1) { left = new TreeNode(2) }; var q = new TreeNode(1) { left = new TreeNode(2) }; var res = IsSameTree(p, q); Console.WriteLine(res); q.right = new TreeNode(6); res = IsSameTree2(p, q); Console.WriteLine(res); Console.ReadKey(); } public static void IsSame(TreeNode p, TreeNode q, ref bool isSameTree) { //先序遍历分析法 if(p?.val != q?.val) { isSameTree = false; return; } if(p != null && q != null) { if(p.left != null || q.left != null) { IsSame(p.left, q.left, ref isSameTree); } if(p.right != null || q.right != null) { IsSame(p.right, q.right, ref isSameTree); } } return; } public static bool IsSameTree(TreeNode p, TreeNode q) { var isSameTree = true; IsSame(p, q, ref isSameTree); return isSameTree; } public static bool IsSameTree2(TreeNode p, TreeNode q) { //优雅递归法 //如果 p 和 q 同时为空,则肯定相 //已经到了递归最底层的调用,也就是递归的最基本情况 //属于递归的终止条件 //以下3行代码均是终止条件 if(p == null && q == null) return true; //如果 p 为空,q 不为空,则肯定不相同 if(p == null) return false; //如果 q 为空,p 不为空,则肯定不相同 if(q == null) return false; //递归调用 return p.val == q.val && IsSameTree2(p.left, q.left) && IsSameTree2(p.right, q.right); } public class TreeNode { public int val; public TreeNode left; public TreeNode right; public TreeNode(int x) { val = x; } } }
以上给出2种算法实现,以下是这个案例的输出结果:
True False
分析:
显而易见,以上2种算法的时间复杂度均为: 。
本文由 .Net中文网 原创发布,欢迎大家踊跃转载。
转载请注明本文地址:https://www.byteflying.com/archives/4066。