101. Symmetric binary tree ‘use of queue, recursive realization of binary tree judgment

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 source: power button (LeetCode) link: https://leetcode-cn.com/problems/symmetric-tree copyright shall belong to the collar of the network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.Copy the code

Their thinking

The recursive implementation

• Mirror symmetry, where the left and right sides are equal, means that the left and right subtrees are equivalent.
• Left subtrees are equal to right subtrees, which means we recursively compare left and right subtrees.
• Special case handling:
  • If the root node is null, it is symmetric;
• DFS (root.left,root.right): recursively compares the left and right nodes of the root node
  • Recursive termination condition;
    • If both nodes are null, they are symmetric.
    • If either node is null, it is asymmetric.
    • The values of the two nodes are not equal. ==right.val, then asymmetric;
    • If the two nodes are equal, the nodes of the two subtrees are equal. Recursive comparison;
    • return dfs(left.left,right.right)&&dfs(left.right,right.left);

code

/** * Definition for a binary tree node. * class TreeNode { * val: number * left: TreeNode | null * right: TreeNode | null * constructor(val? : number, left? : TreeNode | null, right? : TreeNode | null) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } * } */

function isSymmetric(root: TreeNode | null) :boolean {
  // if the root node is null, return true.
    if(root==null) {return true;
    }
  // select * from the left node of the root node;
    return dfs(root.left,root.right);
};
function dfs(left:TreeNode|null,right:TreeNode|null) :boolean{
  // End condition of recursion:
    // if both nodes are null, it is symmetric.
    if(left==null&&right==null) {return true;
    }
    // 4. One of the two nodes is null; Is asymmetric;
    if(left==null||right==null) {return false;
    }
    // the value of val is not equal. The asymmetric
    if(left.val! ==right.val){return false;
    }
    // If the values of the two nodes are equal, perform a recursive comparison
    return dfs(left.left,right.right)&&dfs(left.right,right.left);


}
Copy the code

Queue implementation

Recall the implementation of recursion as follows:

• Give priority to special cases:
  • When the root node is null, it is symmetric.
  • If the left node is null && the right node is null; Symmetry;
• We queue two nodes (left and right) from the queue.
• Through the queue;
  • Compare two nodes of the queue: leftNode,rightNode;
    • If the left and right nodes are equal, the traversal of the current level continues
    • One of the two nodes is null; Is asymmetric;
    • The left and right node values are different; Is asymmetric;
    • The queue is pressed into a new comparison node; Left child of the left node and right child of the right node
    • The queue is pressed into a new comparison node; The right child of the left node and the left child of the right node

Time is O(n), space is O(n).

    function isSymmetric(root: TreeNode | null) :boolean {
    // Give priority to special cases;
        // if the root node is null, it is symmetric.
        // if the left node is null && the right node is null; Symmetry;
    if(root==null||(root.left==null&&root.right==null)) {return true;
    }
    // Otherwise, use queues to store the current comparison level node;
    let queue=[];
    queue.push(root.left);
    queue.push(root.right);
    // Continue the comparison when queue data exists;
    while(queue.length>0) {let leftNode=queue.shift();
        let rightNode=queue.shift();
            //3. If the left and right nodes are equal, continue traversing the current level;
            if(leftNode==null&&rightNode==null) {continue;
            }
            // 4. One of the two nodes is null; Is asymmetric;
            if(leftNode==null||rightNode==null) {return false;
            }
            // 5. The left and right nodes have different values. Is asymmetric;
            if(leftNode.val! ==rightNode.val){return false;
            }
            // 6, otherwise leftNode.val===rightNode.val; All possibilities of the current comparison node are compared.
                // queue is pressed into a new comparison node; Left child of the left node and right child of the right node
            queue.push(leftNode.left);
            queue.push(rightNode.right);
                // queue is pressed into a new comparison node; The right child of the left node and the left child of the right node
            queue.push(leftNode.right);
            queue.push(rightNode.left);
    }

    return true;
    
    };

Copy the code