Leetcode 101/100 - Symmetric tree / Same tree

Note

  • Intuitive way is to use recursion.
  • There are three situations
    • Both are null, which means left subtree and right subtree are the same.
    • One of them is null, so it’s false
    • Both are not null, then we need recursion, comapre val first then use &&. Be careful that we need to compare left.left, right.right and left.right, right.left.

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

Example

img

1
2
Input: root = [1,2,2,3,4,4,3]
Output: true
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {boolean}
*/
var isSymmetric = function(root) {
if (!root) return true;
return compare(root.left, root.right);
};

function compare(left, right) {
if (!left && !right) return true;
if (left && !right || !left && right) return false;
return left.val === right.val && compare(left.left, right.right) && compare(left.right, right.left);
}