I participated in the 21st day of November Gwen Challenge, the event details: 2021 last Gwen Challenge

Given a binary tree, return its backward traversal.

Here are the traversal rules for binary trees:
  • Binary trees have pre-ordered, middle-ordered, and post-ordered traversal. The front, middle, and back are for the root node.
  • The root node is first, as in the preceding traversal:The root On the left right
  • As in middle order traversal, the root node is in the middle, as in:On the left The root right
  • In the case of post-order traversal, the root node is the last, as in:On the left right The root

It is not hard to see that the order of the left and right child nodes remains the same, as long as you know the position of the root node.

Solution 1: recursive thought

     / / monitored
var postorderTraversal = function(root, res = []) {
   if(! root)return res
   postorderTraversal(root.left, res)
   postorderTraversal(root.right, res)
   res.push(root.val)
   return res
}

Copy the code

Solution two: iteration idea

  • First, the idea of iteration is that we need a stack to hold the iterated elements, and then the sequential iterated elements firstpushTheta is the left child node. But we’re going to traverse the root node first, and in that case, we need to push the traversal node onto the stack, and then find its left child until there are no left children. At this point, we need to take a node out of the stack.
const stack = []
let prev = null
while(root || stack.length) { // Root exists and stack is not empty and the loop will continue
    while(root){
        stack.push(root)
        root = root.left // If the left child node always exists, it will always be pushed.
    }
    // There are no left children at this point
    root = stack.pop()  // Remove the top node
    
    // If the right child node is empty
    if(root.right == null || root.right == prev){ // root.right == prev does not iterate over the right child node
        res.push(root.val) // Push the root node in when both sides are empty
        prev = root   // Save the current node
        root = null // let's go to the condition of stack. Length > 0 for the outer loop
    }else{
        // The child node on the left is added first
        res.push(root.val)
        root = root.right // point to the right child node}}Copy the code
The complete code
var postorderTraversal = function(root) {
   if(! root)return []
   const res = []
   const stack = []
   let prev = null
   while(root || stack.length){
       while(root){
           stack.push(root)
           root = root.left
       }
       root = stack.pop()
       if(root.right ==null || root.right == prev){
           res.push(root.val)
           prev = root
           root =null
       }else{
           stack.push(root)
           root = root.right
       }
   }
   return res
}

Copy the code