This is the 7th day of my participation in the November Gwen Challenge. Check out the details: The last Gwen Challenge 2021

📢 preface

  • 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻
  • 🌲 punch in an algorithm every day, which is not only a learning process, but also a sharing process 😜
  • 🌲 tip: the programming languages used in this column are C# and Java
  • 🌲 to maintain a state of learning every day, let us work together to become a god of algorithms 🧐!
  • 🌲 today is the fortieth day of continuous clocking of force button algorithm 🎈!
  • 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻

🌲 Example: Post-order traversal of binary trees

Given a binary tree, return its backward traversal.

Example 1:

Input:1.null.2.3]  
   1
    \
     2
    /
   3Output:3.2.1]
Copy the code

🌻C# method 1: iteration

Use only one stack for the subsequent traversal. The steps are as follows:

  1. Go all the way to the left node;
  2. Push nodes into the stack in the order of root node -> right node -> left node;
  3. When the leaf node is touched, the stack begins to exit;
  4. If the node to which the current top element points still has unaccessed child nodes, go back to Step 1 and repeat.
  5. If the stack is empty, the traversal ends.

The difficulty is how to determine whether the top node has children that are not accessed. If the judgment method is improper, it is likely that the top node of the stack is the parent node of the last out-of-stack node, which leads to the repeated loading and unloading of its nodes into an infinite loop.

You can add a variable or pointer to the last node that has gone off the stack.

Each time to judge the top node of the stack, we only need to judge in advance whether it is the parent-child relationship with the last node that is out of the stack. If it is, we will continue to out the stack. Otherwise, we will go back to step 1 above to carry out the loading cycle.

public class Solution {
    public IList<int> PostorderTraversal(TreeNode root) {
        List<int> rst = new List<int> ();if(root == null) return rst;

        Stack<TreeNode> st = new Stack<TreeNode>();
        TreeNode node = root;
        TreeNode printNode = root;
        TreeNode tmp = null;
        st.Push(node);
        while(st.Any())
        {
            tmp = null;
            if(node.left ! = printNode && node.right ! = printNode) {if(node.right ! =null)
                {
                    st.Push(node.right);
                    tmp = node.right;
                }
                if(node.left ! =null)
                {
                    st.Push(node.left);
                    tmp = node.left;
                }
            }
            node = tmp;
            if(tmp == null)
            {
                rst.Add((printNode = st.Pop()).val);
                if(st.Any()) node = st.Peek(); }}returnrst; }}Copy the code

The execution result

The execution time was 284ms, and the memory consumption was 30.1MB.

🌻Java Method 1: Recursion

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

Define postorder(root) to represent the answer currently traversed to the root node. By definition, we recursively call postorder(root->left) to traverse the left subtree of the root node, then recursively call postorder(root->right) to traverse the right subtree of the root node, and add the value of root to the answer. Recursion terminates when an empty node is encountered.

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        postorder(root, res);
        return res;
    }

    public void postorder(TreeNode root, List<Integer> res) {
        if (root == null) {
            return; } postorder(root.left, res); postorder(root.right, res); res.add(root.val); }}Copy the code

Result The operation succeeds

Execution takes0Ms, beat out all Java commits100.00% of user memory consumption36.6MB, beat out all Java commits68.49% of the userCopy the code

🌻Java Method 2: Iteration

The general idea is that we can also implement the recursive function of method 1 iteratively. The two methods are equivalent, but the difference is that the recursion implicitly maintains a stack.

We need to simulate the stack explicitly during iteration, and the rest of the implementation and details are the same, as shown in the code below.

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        if (root == null) {
            return res;
        }

        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        TreeNode prev = null;
        while(root ! =null| |! stack.isEmpty()) {while(root ! =null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            if (root.right == null || root.right == prev) {
                res.add(root.val);
                prev = root;
                root = null;
            } else{ stack.push(root); root = root.right; }}returnres; }}Copy the code

The execution result

Result The operation succeeds

Execution takes0Ms, beat out all Java commits100.00% of user memory consumption36.7MB, beat out all Java commits40.52% of the userCopy the code

💬 summary

  • Today is the fortieth day of buckle algorithm clocking!
  • This paper uses C# and Java programming languages to solve the problem
  • Some methods are also written by the god of reference force buckle, and they are also shared while learning, thanks again to the algorithm masters
  • That’s the end of today’s algorithm sharing, see you tomorrow!