This series is nothing fancy, just pure Leetcode problem breakdown analysis, not to use a sexy line or a niche solution, but with clear code and simple enough thinking to help you clarify the problem. Let you in the interview no longer afraid of algorithm written test.

76. The same tree

The label

  • Binary tree
  • simple

The title

Leetcode portal

Let’s just open leetCode.

Given the root nodes p and q of two binary trees, write a function to check whether the two trees are the same.

Two trees are considered identical if they are structurally identical and the nodes have the same value.

Input: p = [1,2,3], q = [1,2,3] output: trueCopy the code

The basic idea

There’s nothing to say here, just a binary tree recursive comparison.

Writing implement

var isSameTree = function(p, q) {
  // are null and equal
  if (p === null && q === null) {
    return true
  } else if(p ! = =null&& q ! = =null) {
    if(p.val ! == q.val) {return false
    } else {
      // Compare left and right subtrees recursively
      return isSameTree(p.left, q.left) && isSameTree(p.right, q.right)
    }
  } else {
    // This is a null branch and a non-null branch
    return false}};Copy the code

77. Symmetric binary tree

The label

  • Binary tree
  • simple

The title

Leetcode portal

Let’s just open leetCode.

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 3Copy the code

The basic idea

The same problem we had with binary tree traversal, and we want to get a sense of it

This article is very clear, [algorithm disassembly] article said through binary tree traversal routine

We should also pay more attention to develop several important skills at ordinary times: disassembling problems and transformation problems (mathematically called substitution)

This is to check if a tree is mirror symmetric so we can substitute: the tree looks like itself when flipped.

So the problem breaks down to

  • Flip the binary tree
  • Determine two binary trees (Original tree & flipped tree)Are equal(That’s the one above)

That’s one way to think about it

In addition, the above judgment is equal and similar, directly to the logical analysis.

  • I’m going to recursively determine whether the left and right subtrees are symmetric
  • The exit is determined by null

Writing implement

First implement the down flipped binary tree, reference the above article method

const invertTree = (root) = > {
  if (root === null) {
    return null;
  }
  
  // Access the root first and swap the left and right subtrees here
  // ES6 destruct assignment is used
  [root.left, root.right] = [root.right, root.left]
  
  // Then traverse the left subtree
  invertTree(root.left)         // --------->
  // Walk through the right subtree again
  invertTree(root.right)        // --------->
  
  return root
}
Copy the code

I’m not going to write it, but it’s very simple, so let’s do the second idea.

var isSymmetric = function(root) {
  const isMirror = (tree1, tree2) = > {
    // Recursive exit
    if (tree1 === null && tree2 === null) {
      return true
    }
    // Since both of the above are excluded, the following one is null, which is definitely not symmetric
    if (tree1 === null || tree2 === null) {
      return false
    }
    // Then determine whether the left and right subtrees are symmetric, first root, then recursively determine the left and right subtrees
    Return true if the root is symmetric and the corresponding nodes of the left and right subtrees are symmetric
    if (tree1.val === tree2.val 
      && isMirror(tree1.left, tree2.right) 
      && isMirror(tree1.right, tree2.left)) {
      return true
    } else {
      return false}}return isMirror(root, root)
};
Copy the code

In addition, I would like to recommend the article of the eldest brother to you. It is very simple and profound. It is very effective for the students who advance in the front end. Core concepts and algorithm disassembly series

That’s all for today. If you want to work with me, you can add me to my wechat account infinity_9368, and you can chat with me and add my secret code “Tianwang Gedi Hu”. Verify the message please send me presious tower shock the rever monster, I see it through, the code is not on the ha, add after I will do my best to help you, but pay attention to the way of asking questions, suggest reading this article first: the wisdom of asking questions

reference

  • Juejin. Cn/post / 690713…