Symmetric Tree
Leetcode #101 | Easy | Деревья | DFS | BFS
Идея
DFS на сравнение детей. Если оба null - true, если только один или значения разные - false, потом рекурсивно+перекрестно (то есть левый1 с правым2 и левый2 с правым1). Можно и BFS-ом, тоже перекрестно складывая по парам. Такой двойной дфс.
Big-O
- Время
O(N) - Память
O(H)
N - количество узлов, H - высота дерева
Код
class Solution {
public boolean isSymmetric(TreeNode root) {
return root == null || isMirror(root.left, root.right);
}
private boolean isMirror(TreeNode t1, TreeNode t2) {
if (t1 == null && t2 == null) return true;
if (t1 == null || t2 == null || t1.val != t2.val) return false;
return isMirror(t1.left, t2.right) && isMirror(t1.right, t2.left);
}
}