Hello, everyone. Today, I would like to share with you the next simple and difficult problem of LeetCode 226. Flip the binary tree

The title

Flip a binary tree. (Image from LeetCode)

Analysis of the

1. The binary tree

2. Switch nodes on the left and on the right

3. Return the array

solution

* 1. Recursion

2. The iteration

Solution a:recursive

Train of thought1.Recursion from top to bottom2.Each layer switches nodes */var invertTree = function (root) {
  if(! root)return root;
  const { left, right } = root;
  root.left = right;
  root.right = left;
  invertTree(root.left);
  invertTree(root.right);

  return root;
};
// @lc code=end

/* Complexity time O(n) space O(n) */
Copy the code

Solution two: iteration

Train of thought1.Using stack, switch left and right child nodes from top to bottom2.Put the left and right nodes on the stack3.Stack. pop Remove the node and repeat1
4.Return node root */var invertTree = function (root) {
  if(! root)return root;
  const stack = [];
  stack.push(root);
  while (stack.length) {
    const node = stack.pop();
    const { left, right } = node;
    // Swap child nodes
    node.left = right;
    node.right = left;

    // Check whether a node exists and add it to the stack
    if (node.right) stack.push(node.right);
    if (node.left) stack.push(node.left);
  }

  return root;
};
/* Complexity time O(n) space O(n) */
Copy the code

conclusion

Today’s problem is mainly to practice the understanding of recursion and how to use stack to simulate internal recursion

You can have a look at a column I share (front-end algorithm) where there are more topics about the algorithm to share, I hope to help you, I will try to keep updated every night, if you like the trouble to help me to like, thank you very much

If you’re interested in “TS” check out my column (TypeScript common knowledge) and thank you for supporting it

The purpose of this article is to study, discuss and share the experience in the process of learning algorithm. Some of the materials in this article are from the network. If there is infringement, please contact to delete, [email protected]