“This is the 28th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

Title 1

226. Flipping binary trees

Flip a binary tree.

Example:

Input:

4 / \ 27 / \ / \ 1 3 6 9Copy the code

Output:

4 / \ 7 2 / \ / 9 6 3 1Copy the code

Ask questions

  • What is a flipped binary tree?
  • How to implement flipped binary tree?

Analysis of the

  • A flipped binary tree is one where the left and right child nodes interact with each other
  • Recursively traverse the binary tree, traversing the left and right child nodes interact with each other

Pseudo code

  • In the first place to judgerootWhether it isnullfornullDirect returnnull
  • Recurse to the left and right nodes of the front node and assign toL, rvariable
  • makeroot.left = r.root.right = l
  • returnroot

Code implementation

/** * 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 {TreeNode} */ var invertTree = function(root) { if(! root) return null let l = invertTree(root.left) let r = invertTree(root.right) root.left = r root.right = l return root };Copy the code

Topic 2

102. Sequence traversal of binary trees

Given a binary tree, return the values of nodes traversed in order. (That is, layer by layer, all nodes are accessed from left to right).

 

Example: binary tree: [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
   
Copy the code

Return the sequence traversal result:

[[3], [9,20], [15,7]

Ask questions

  • How are binary trees sequenced?

Analysis of the

  • Recursively traverses the binary tree one at a time, and putspushI didn’t recurse one level in the arraykAdd 1

Pseudo code

  • To define aarrStore the sequence results
  • To define agetResultMethod used in thearr pushOf the current binary tree nodeval, the three parameters of this method are respectivelyroot,k,arr
  • In the first place to judgerootWhether it isnullfornullDirect returnnull
  • Judgment levelkWhether or notarrArray lengthlengthIs it the same? If it is, goarrvariablearr.push(new Array())
  • And put the current noderootThe value of theval pushtoarr[k]
  • Recursive callsgetResultMethod is passed to the left and right nodes of the front node and thek+1

Code implementation

/** * 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 {number[][]} */ var levelOrder = function(root) { let arr = [] getResult(root,0,arr) return arr }; var getResult = function (root,k,arr){ if(! root) return null if(k == arr.length) arr.push(new Array()) arr[k].push(root.val) getResult(root.left, k+1 ,arr) getResult(root.right, k+1 ,arr) }Copy the code