【 Say little 】

Leecode 145. Post-order traversal of binary trees

Given a binary tree, return its backward traversal.

Example:

Input: [1, null, 2, 3]

Output: [3, 2, 1]

First we need to understand what a binary tree is: we walk through the tree in the same way as we visit the left subtree — the right subtree — the root node. We walk through the tree in the same way as we visit the left subtree or the right subtree until we walk through the entire tree. Therefore, the whole traversal process naturally has the nature of recursion, we can directly use recursive function to simulate this process.

Reference code

Define a tree

Struct {* Val int Left *TreeNode // Left * Right *TreeNode // right node *} */Copy the code

  1. If null, go postorder(node.right). If there is still a left node on the Right, continue to go to the left node until you reach the left node on the bottom. Take the third step and then debrand the left node into the array.

  2. Return to the right node, then descript into the array

  3. Discards the root node into the array.

GO language version of recursion

func postorderTraversal(root *TreeNode) (res []int) {
    var postorder func(*TreeNode)
    postorder = func(node *TreeNode) {
        if node == nil {
            return
        }
        postorder(node.Left)  //  1
        postorder(node.Right)  / / 2
        res = append(res, node.Val)  / / 3
    }
    postorder(root)
    return
}



Copy the code

Iteration stack for GO language version: First in last out

Define a stack STK that stores a tree

1. Untag the root node into the array and then run through the left subtree to find the bottom left node.

2. Pop out the last node on the stack

3. If the left node is not empty or the right node is not empty, the node is added to the stack

4. If it is empty, the root node is either the left node or the right node. If the left node exits the stack first, then the left node is detested into the array and the right node is detested until the last root node.

func postorderTraversal(root *TreeNode) (res []int) {
    stk := []*TreeNode{} 
    var prev *TreeNode
    forroot ! =nil || len(stk) > 0 {
        forroot ! =nil {
            stk = append(stk, root)  / / 1.
            root = root.Left
        }
        root = stk[len(stk)- 1]
        stk = stk[:len(stk)- 1] / / 2.
        if root.Right == nil || root.Right == prev { / / 3.
            res = append(res, root.Val) / / 4.
            prev = root
            root = nil
        } else {
            stk = append(stk, root)
            root = root.Right
        }
    }
    return
}


Copy the code