首页 > 代码库 > LeetCode: isSameTree1 解题报告
LeetCode: isSameTree1 解题报告
isSameTree1
Given two binary trees, write a function to check if they are equal or not.
Two binary trees are considered equal if they are structurally identical and the nodes have the same value.
SOLUTION 1 & SOLUTION 2:
以下是递归及非递归解法:
1. 递归解法就是判断当前节点是不是相同，及左右子树是不是相同树
2. 非递归解法使用了先根遍历。这个算法比较简单一点
1 /** 2 * Definition for binary tree 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode(int x) { val = x; } 8 * } 9 */10 public class Solution {11 // solution 1:12 public boolean isSameTree1(TreeNode p, TreeNode q) {13 if (p == null && q == null) {14 return true;15 }16 17 if (p == null || q == null) {18 return false;19 }20 21 return p.val == q.val &&22 isSameTree(p.left, q.left) &&23 isSameTree(p.right, q.right);24 }25 26 // Solution 2:27 public boolean isSameTree(TreeNode p, TreeNode q) {28 if (p == null && q == null) {29 return true;30 }31 32 if (p == null || q == null) {33 return false;34 }35 36 Stack<TreeNode> s1 = new Stack<TreeNode>();37 Stack<TreeNode> s2 = new Stack<TreeNode>();38 39 s1.push(p);40 s2.push(q);41 42 while (!s1.isEmpty() && !s2.isEmpty()) {43 TreeNode cur1 = s1.pop();44 TreeNode cur2 = s2.pop();45 46 // 弹出的节点的值必须相等 47 if (cur1.val != cur2.val) {48 return false;49 }50 51 // tree1的right节点，tree2的right节点，可以同时不为空，也可以同时为空，否则返回false.52 if (cur1.left != null && cur2.left != null) {53 s1.push(cur1.left);54 s2.push(cur2.left);55 } else if (!(cur1.left == null && cur2.left == null)) {56 return false;57 }58 59 // tree1的左节点，tree2的left节点，可以同时不为空，也可以同时为空，否则返回false.60 if (cur1.right != null && cur2.right != null) {61 s1.push(cur1.right);62 s2.push(cur2.right);63 } else if (!(cur1.right == null && cur2.right == null)) {64 return false;65 }66 }67 68 return true;69 }70 }
GITHUB:
https://github.com/yuzhangcmu/LeetCode_algorithm/blob/master/tree/IsSameTree1.java
LeetCode: isSameTree1 解题报告
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。