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

145. Backward traversal of binary trees

Given a binary tree, return its backward traversal.

Example:

Enter: [1, NULL,2,3] 1 2/3

Output: [3,2,1] advanced: the recursive algorithm is very simple, can you do it with an iterative algorithm?

Answer key

Ask questions

  • What is a posterior traversal of a binary tree?

Analysis of the

  • We start at the left node, we walk through the subtree and when we’re done, we walk through the right subtree, and then we walk through the root node
  • Formula: Preorder traversal: left -> right -> root

Recursive analysis

  • defineansUsed to store the value of traversing the binary tree
  • definetraversalMethod is used to achieve binary tree traversal
  • traversalThe method starts withrootMake a non-null judgment whenrootReturns directly if nullnull
  • Otherwise apply the formula
  • First the recursive calltraversal(root.left,ans)The left subtree is alreadytraversal(root.right,ans)The right subtree
  • againpushValue of the root node
  • Finally, the binary tree after the order traversal

Recursive 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 postorderTraversal = function(root) { let ans = [] traversal(root,ans) return ans }; let traversal = function(root,ans){ if(! root) return null traversal(root.left,ans) traversal(root.right,ans) ans.push(root.val) }Copy the code

Iterative analysis

  • In addition to the recursive approach, we can also use an iterative approach
  • definestackStack, used to store the current node of the binary tree
  • defineansUsed to store the value of traversing the binary tree
  • First of all,rootMake a non-null judgment whenrootNot null pushes the current root node onto the stackunshift
  • throughwhileLoop through the stack untilstackIs null
  • Because the traversal formula of the anteorder binary tree is anteorder traversal: left -> right -> root, and at this timestackStack (first in, last out) to store all we should first put the left subtreepushPush, and put the right subtreepushInto the stack
  • Through constantwhileLoop to perform the above operations
  • Finally, the binary tree after the order traversal

Iterative 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 postorderTraversal = function(root) { let stack =  [] let ans = [] if(root) stack.push(root) while(stack.length > 0){ const curNode = stack.pop() ans.unshift(curNode.val)  if(curNode.left ! == null ){ stack.push(curNode.left) } if(curNode.right ! == null ){ stack.push(curNode.right) } } return ans };Copy the code