Binary trees and recursion

101. Symmetric binary trees are simple

Topic describes

Given a binary tree, check whether it is mirror - symmetric. For example, binary trees [1,2,2,3,4,4,3] are symmetric. 1 / \ 2 2 / \ / 3 4 4 3 But the following [1,2,2,null,3,null,3] is not mirror symmetric: 1 / \ 2 2\3 3 progression: can you use both recursion and iteration to solve this problem?Copy the code

Solution:

First, the recursive

var isSymmetric = function (root) {
    return dfs(root, root)

    function dfs(p, q) {
        if(! p && ! q)return true
        // False when one exists and the other does not
        if(! p || ! q)return false
        // The left most corresponds to the right most
        return p.val == q.val && dfs(q.left, p.right) && dfs(q.right, p.left)
    }
};
Copy the code

Solution:

The iteration

var isSymmetric = function (root) {
    return iterator(root, root);

    function iterator(l, r) {
        let queue = [l, r];
        while (queue.length) {
            r = queue.pop();
            l = queue.pop();

             // The iterator returns the value of the iterator
            if(! r && ! l)continue

            if(! r || ! l || l.val ! = r.val) {return false;
            }

            queue.push(l.left);
            queue.push(r.right);

            queue.push(l.right);
            queue.push(r.left);
        }
        return true; }};Copy the code

Punch a wave 😄