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

Given a binary tree, return its backward traversal.

Example:

Input: [1, NULL,2,3] 1\2/3 Output: [3,2,1]Copy the code

Advanced: The recursive algorithm is simple, can you do it with an iterative algorithm?

Since recursion is easy, let’s start with simple recursion

recursive

First of all, we need to understand what is the post-order traversal of the binary tree, traversing the tree in the way of left → right → root node, the result is the post-order traversal of the binary tree. When accessing the subtrees, both the left and right subtrees should be traversed in this order. Until the whole tree is complete. This whole traversal process, it seems, is inherently recursive, so when we first look at it, we think of recursive methods.

We define a postorder(root) to represent the root node currently traversed. The left subtree, root.left, is recursively traversed, and the right subtree, root.right, is recursively traversed, and the root node is recorded. The termination condition is root traversal.

function postorder(root, res=[]){ if(! root) return; postorder(root.left,res); postorder(root.right,res); res.push(root.val) return res; }Copy the code

Complexity analysis

  • Time complexity: O(n), where n is the number of nodes in the binary search tree. Each node is traversed exactly once.
  • Spatial complexity: O(n), is the stack overhead in the recursive process, O(log⁡n) in the average case, O(n) in the worst case, the tree chain-like, O(n).

Now that the recursive approach has been figured out, it’s natural to challenge the iterative approach.

An iterative approach

Since the problem requires it, we can use the iterative method to do it. The two approaches are essentially equivalent, except that in recursion we implicitly maintain a stack, while in iteration we simulate the stack.

↙ ↘ 9 4 ↘ 5 7Copy the code

Let’s take the binary tree above. We press middle → right → left to push, then out of the stack order is left → right → middle. But when we iterate, we can’t resolve the inconsistency between accessing the node (traversing the node) and processing the node (putting elements into the result set) at the same time. So we’re going to put the nodes we’re going to visit on the stack, and we’re going to put the nodes we’re going to process on the stack but we’re going to mark them. To mark a node, a null pointer is placed immediately after the node is placed on the stack. This method can also be called notation.

  • Create a new stack [] with res = []

  • 3. Push, [3]

  • Push the empty node, which means that 3 has visited. stack=[3,null]

  • Stack = [3, null, 4]

  • Stack =[3, null, 4, 9]

  • At the end of the first loop, if the stack is not empty, fetch the top element.

  • Stack =[3, null, 4, 9, null]

  • The loop ends when the left and right child nodes do not exist.

  • If the stack is not empty, fetch the top element of the stack. Node =null indicates that the access to an element is complete and the stack needs to be removed.

  • Take the top element, 9, and pass it into res, res=[9]. End of loop.

  • If stack is not empty, fetch the top element. Node =4, indicating no access, 4 is pushed. Add flag stack=[3, NULL, 4, null]

  • Judge, left and right child nodes exist, push. Stack =[3, null, 4, null,7,5]. End of loop.

  • Stack =[3, NULL, 4, NULL, 7, 5, NULL]

  • Determine that the left and right child nodes are empty and enter the next loop.

  • Stack =[3, NULL, 4, null, 7]; Res = [9, 5]. Enter the next loop.

  • Stack =[3, NULL, 4, NULL, 7, NULL];

  • Determine that the left and right child nodes are empty and enter the next loop.

  • Stack =[3, null, 4, null,]; Res = [9, 5, 7]. Enter the next loop.

  • Stack =[3, null]; Res =,5,7,4 [9]. Enter the next loop.

  • Remove the top element of the stack, judge that it is empty, and remove the top element of the stack=[]. Res =,5,7,4,3 [9]. Enter the next loop.

  • If the stack is empty, the traversal is complete. Returns the res

    var postorderTraversal = function(root, res = []) { const stack = []; if (root) stack.push(root); while(stack.length) { const node = stack.pop(); if(! Res.push (stack.pop().val); continue; } stack.push(node); / / in the stack. Push (null); // The node has been accessed, but has not been processed. if (node.right) stack.push(node.right); // right if (node.left) stack.push(node.left); / / left}; return res; };

Complexity analysis

  • Time complexity: O(n), where n is the number of nodes in the binary search tree. Each node is traversed exactly once.
  • Spatial complexity: O(n), is the overhead of explicit stack in the iterative process, O(logn) in the average case, O(n) in the worst-case tree chain-like, O(n).