subject

leetcode Original link

Give you the root node of a binary tree root , Returns the After the sequence traversal .

Example 1：

Input ：root = [1,null,2,3]
Output ：[3,2,1]

Example 2：
Input ：root = []
Output ：[]

Example 3：
Input ：root = [1]
Output ：[1]

Tips ：
The number of nodes in the tree is in the range [0, 100] Inside
-100 <= Node.val <= 100

Ideas

• Recursive writing
  • The function parameters are the current binary tree node and an array used to store the results
  • The termination condition is that the node is empty
  • The order of traversal after binary tree is “ Right and left ”, Therefore, single-layer recursive logic is to recurse the left node first , Recursive right node , Finally, the value of the intermediate node is stored in the result array .
• Iterative writing
  • Iterative writing can first look at the iterative writing of preorder traversal 【leetcode】144. Preorder traversal of two tree , The order of precedence traversal is “ Around the middle ”, The order of subsequent traversal is “ Right and left ”, Exchange the traversal order of the left node and the right node in the preorder traversal , become " Center right left ", Then invert the result array to get “ Right and left ”.
  • The code only needs to be changed slightly based on the previous traversal .

Code

• recursive

/** * 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) {
    
    function traversal(node , ans){
    
        if(!node) return 
        //  Recursive left node 
        traversal(node.left , ans)
        //  Recursive right node 
        traversal(node.right , ans)
        //  Store the value of the intermediate node into the result array 
        ans.push(node.val)
    }

    let ans = []
    traversal(root , ans)
    return ans
};

• iteration

/** * 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) {
    
    if(!root) return []
    let stack = []
    let ans = []
    queue.push(root)
    while(stack.length){
    
        const node = stack.pop()
        //  The intermediate node value is added to the result array 
        ans.push(node.val)
        //  Left node first stack 
        if(node.left) stack.push(node.left)
        //  Right node back into the stack 
        if(node.right) stack.push(node.right)
    }

    //  After the result array is flipped, it returns 
    return ans.reverse()
};

Pay attention to my special column , Update three times a day leetcode Answer key , Get stronger together ！