内容简介:给定两个二叉树,编写一个函数来检验它们是否相同。如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。示例 1:
题目
给定两个二叉树,编写一个函数来检验它们是否相同。
如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。
示例 1:
输入: 1 1 / \ / \ 2 3 2 3 [1,2,3], [1,2,3] 输出: true
示例 2: 输入: 1 1 / \ 2 2 [1,2], [1,null,2] 输出: false
示例 3:: 输入: 1 1 / \ / \ 2 1 1 2 [1,2,1], [1,1,2] 输出: false
题解
大多数的二叉树题目都是用递归可以解的。
所以当拿到二叉树的题目的时候,我们首先就是看看能拆解成哪些子问题。
这个问题的子问题很简单,就是左子树,右子树都相等的二叉树是相同的二叉树。
/** * 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; } else if (p == null || q == null) { return false; } if (p.val == q.val) { return isSameTree(p.left, q.left) && isSameTree(p.right, q.right); } else { return false; } } }
那如果用非递归解怎么解呢?
如果遇到二叉树的问题,没思路还有第二招,就是 想想看是不是遍历的变种 :
- 先序遍历
- 中序遍历
- 后序遍历
- 层次遍历
我们可以用队列,一起进行层序遍历,同时比较左右两颗树:
/** * 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; } else if (p == null || q == null) { return false; } LinkedList<TreeNode> queue = new LinkedList<>(); queue.add(p); queue.add(q); while(!queue.isEmpty()) { TreeNode left = queue.poll(); TreeNode right = queue.poll(); if (left == null && right == null) { // 都是空的,遍历到叶子节点了 continue; } else if (left == null || right == null) { // 有一个为null return false; } else if (left.val != right.val) { // 不相等. return false; } // 左子树入队 queue.add(left.left); queue.add(right.left); // 右子树入队 queue.add(left.right); queue.add(right.right); } return true; } }
其实我们本质上就是要比较左右两棵树,也没必要非要是队列,其实stack也是可以的,大同小异。所以并不是你记住哪种数据结构,关键是你能理解后,灵活应用.
public boolean isSameTree(TreeNode p, TreeNode q) { if (p == null && q == null) { return true; } else if (p == null || q == null) { return false; } Stack<TreeNode> stack = new Stack<>(); stack.push(p); stack.push(q); while(!stack.isEmpty()) { TreeNode left = stack.pop(); TreeNode right = stack.pop(); if (left == null && right == null) { continue; } else if (left == null || right == null) { return false; } else if (left.val != right.val) { return false; } stack.push(left.left); stack.push(right.left); stack.push(left.right); stack.push(right.right); } return true; }
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。