Leetcode
Tree
Depth-first Search
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
Example 2:
Input: 1 1 / 2 2 [1,2], [1,null,2] Output: false
Example 3:
Input: 1 1 / / 2 1 1 2 [1,2,1], [1,1,2] Output: false
分析¶
最初想到的就是一一比对二叉树的根节点、左节点和右节点,如果发现不想等的地方,则返回false;
public boolean isSameTree(TreeNode p, TreeNode q) { if (p == null || q == null) return p == q; Queue<TreeNode> queueP = new LinkedList<>(), queueQ = new LinkedList<>(); queueP.add(p); queueQ.add(q); while (!queueP.isEmpty() && !queueQ.isEmpty()) { if (queueP.peek().val != queueQ.peek().val) return false; TreeNode curP = queueP.poll(), curQ = queueQ.poll(); if (curP.left == null) { if (curQ.left != null) return false; } else { queueP.add(curP.left); queueQ.add(curQ.left); } if (curP.right == null) { if (curQ.right != null) return false; } else { queueP.add(curP.right); queueQ.add(curQ.right); } } return queueP.isEmpty() && queueQ.isEmpty(); }
然后写了个递归版本:
public boolean isSameTree(TreeNode p, TreeNode q) { if (p == null || q == null) return p == q; if (p.val != q.val) return false; if (!isSameTree(p.left, q.left)) return false; if (!isSameTree(p.right, q.right)) return false; return true; }
递归真的是太简洁了!!!!而且运算时间还快!对于树的题目来说,还是写递归好。
近期评论