拓展：用栈模拟递归迭代遍历二叉树

Info

已完成网站教程、网站习题、配套插件中所有多语言代码的校准，解决了之前 chatGPT 翻译可能出错的问题~

Here is the English translation of the provided content:

Prerequisites

Before reading this article, you need to learn:

• Binary Tree Basics
• DFS/BFS Traversal of Binary Trees

This Content is for Extension Only

Generally, recursive traversal or level-order traversal is sufficient for handling binary trees.

The stack-based iterative traversal method introduced in this article is essentially a manual simulation of the recursive process using a stack. This method is not required for other problems on this website, and it is also rarely asked in interviews.

Therefore, the content of this article is solely for expanding your thinking, and you are not required to master it. If you are not interested, feel free to skip the content of this article.

DFS/BFS Traversal of Binary Trees introduced recursive traversal and level-order traversal methods for binary trees, which are the simplest and most practical methods.

Some readers have asked me how to convert the recursive framework for preorder, inorder, and postorder traversals into an iterative form. I used to memorize some code templates for implementing iterative preorder, inorder, and postorder traversals of binary trees. These templates are relatively short and easy to remember, but they lack generality.

Lacking generality means that the templates are only designed for the specific problem of "using an iterative approach to return the preorder/inorder/postorder traversal results of a binary tree," with a function signature similar to this, returning a list of TreeNode:

java 🟢

List<TreeNode> traverse(TreeNode root);

cpp 🤖

vector<TreeNode*> traverse(TreeNode* root);

python 🤖

def traverse(root: TreeNode) -> List[TreeNode]:

go 🤖

func traverse(root *TreeNode) []*TreeNode

javascript 🤖

var traverse = function(root) {
};

If given some slightly more complex binary tree problems, such as Lowest Common Ancestor or Maximum Sum of Binary Search Subtree Keys, you might find it challenging to convert these recursive solutions into iterative ones.

What I want is a universal template that can transform any binary tree recursive algorithm into an iterative one.

In other words, something similar to a binary tree recursive framework:

java 🟢

void traverse(TreeNode root) {
    if (root == null) return;
    // the position of preorder traversal code
    traverse(root.left);
    // the position of inorder traversal code
    traverse(root.right);
    // the position of postorder traversal code
}

cpp 🤖

void traverse(TreeNode* root) {
    if (root == NULL) return;
    // the position of preorder traversal code
    traverse(root->left);
    // the position of inorder traversal code
    traverse(root->right);
    // the position of postorder traversal code
}

python 🤖

def traverse(root):
    if not root:
        return
    # the position of preorder traversal code
    traverse(root.left)
    # the position of inorder traversal code
    traverse(root.right)
    # the position of postorder traversal code

go 🤖

func traverse(root *TreeNode) {
    if root == nil {
        return
    }
    // the position of pre-order traversal code
    traverse(root.Left)
    // the position of in-order traversal code
    traverse(root.Right)
    // the position of post-order traversal code
}

javascript 🤖

var traverse = function(root) {
    if (root === null) return;
    // the position of preorder traversal code
    traverse(root.left);
    // the position of inorder traversal code
    traverse(root.right);
    // the position of postorder traversal code
};

The iterative framework should also have positions for pre-order, in-order, and post-order code:

java 🟢

void traverse(TreeNode root) {
    while (...) {
        if (...) {
          // the position of preorder traversal code
        }
        if (...) {
          // the position of inorder traversal code
        }
        if (...) {
          // the position of postorder traversal code
        }
    }
}

cpp 🤖

void traverse(TreeNode* root) {
    while (...) {
        if (...) {
          // the position of preorder traversal code
        }
        if (...) {
          // the position of inorder traversal code
        }
        if (...) {
          // the position of postorder traversal code
        }
    }
}

python 🤖

def traverse(root: TreeNode):
    while (...):
        if (...):
          # code position for pre-order traversal
        if (...):
          # code position for in-order traversal
        if (...):
          # code position for post-order traversal

go 🤖

func traverse(root *TreeNode) {
    for .... {
        if ... {
            // the position of preorder traversal code
        }
        if ... {
            // the position of inorder traversal code
        }
        if ... {
            // the position of postorder traversal code
        }
    }
}

javascript 🤖

var traverse = function(root) {
    while (...) {
        if (...) {
          // the position of preorder traversal code
        }
        if (...) {
          // the position of inorder traversal code
        }
        if (...) {
          // the position of postorder traversal code
        }
    }
}

If I want to convert recursion to iteration, I can simply copy and paste the code from the recursive solution's pre-order, in-order, and post-order positions into the iterative framework, and it will run correctly.

Theoretically, all recursive algorithms can be converted to iterative forms using a stack, because computers essentially use stacks to iteratively execute recursive functions.

Therefore, this article will use a 'stack' to simulate the process of function recursion and summarize a general iterative traversal framework for binary trees.

Converting Recursive Framework to Iterative

According to Dong's Guide to Binary Trees (Overview), in the recursive framework of binary trees, the pre-order, in-order, and post-order traversal positions are specific time points:

• The pre-order traversal code is executed right when we first reach the current node root, before traversing root's left and right subtrees.
• The in-order traversal code is executed after traversing the current node root's left subtree and before starting to traverse root's right subtree.
• The post-order traversal code is executed after traversing the entire subtree rooted at the current node root.

If we look at the recursive code, these conclusions are easy to understand:

java 🟢

void traverse(TreeNode root) {
    if (root == null) return;
    // the position of preorder traversal code
    traverse(root.left);
    // the position of inorder traversal code
    traverse(root.right);
    // the position of postorder traversal code
}

cpp 🤖

void traverse(TreeNode* root) {
    if (root == NULL) return;
    // the position of preorder traversal code
    traverse(root->left);
    // the position of inorder traversal code
    traverse(root->right);
    // the position of postorder traversal code
}

python 🤖

def traverse(root):
    if not root:
        return
    # the position of preorder traversal code
    traverse(root.left)
    # the position of inorder traversal code
    traverse(root.right)
    # the position of postorder traversal code

go 🤖

func traverse(root *TreeNode) {
    if root == nil {
        return
    }
    // the position of pre-order traversal code
    traverse(root.Left)
    // the position of in-order traversal code
    traverse(root.Right)
    // the position of post-order traversal code
}

javascript 🤖

var traverse = function(root) {
    if (root === null) return;
    // the position of preorder traversal code
    traverse(root.left);
    // the position of inorder traversal code
    traverse(root.right);
    // the position of postorder traversal code
};

However, if we want to convert a recursive algorithm into an iterative one, we can't just understand the logic from the framework; we need to delve into the details and think about how the computer performs recursion.

Suppose the computer runs function A; it places A in the call stack. If A calls function B, then B is placed on top of A. If B calls C, then C is placed on top of B, and so on...

When C finishes executing, it is popped from the stack, and its return value is passed to B. After B completes, it is popped from the stack, and its return value is passed to A. Finally, when A finishes, it returns the result and is popped from the stack, leaving the call stack empty and ending the entire function call chain.

Our recursive binary tree traversal function works the same way. When the function is called, it is pushed onto the call stack, and when it ends, it is popped from the call stack.

Based on this, we can write the following code to simulate the process of recursive calls:

java 🟢

// Simulate the system's function call stack
Stack<TreeNode> stk = new Stack<>();

void traverse(TreeNode root) {
    if (root == null) return;
    // Push to the call stack when the function starts
    stk.push(root);
    traverse(root.left);
    traverse(root.right);
    // Leave the call stack when the function ends
    stk.pop();
}

cpp 🤖

#include<stack>
using namespace std;

stack<TreeNode*> stk;

void traverse(TreeNode* root) {
    if (root == nullptr) return;
    // push onto the call stack at the beginning of the function
    stk.push(root);
    traverse(root->left);
    traverse(root->right);
    // leave the call stack when the function ends
    stk.pop();
}

python 🤖

# Simulating the system's function call stack
stk = []

def traverse(root: TreeNode):
    if root is None:
        return
    # Push to the call stack when the function starts
    stk.append(root)
    traverse(root.left)
    traverse(root.right)
    # Leave the call stack when the function ends
    stk.pop()

go 🤖

func traverse(root *TreeNode) {
    // simulate the system's function call stack
    var stk []*TreeNode

    var dfs func(*TreeNode)
    dfs = func(node *TreeNode) {
        if node == nil {
            return
        }
        // push onto the call stack when the function starts
        stk = append(stk, node)
        defer func() {
            // leave the call stack when the function ends
            stk = stk[:len(stk)-1]
        }()

        dfs(node.Left)
        dfs(node.Right)
    }

    dfs(root)
}

javascript 🤖

// Simulate the system's function call stack
var stk = [];

function traverse(root) {
    if (root === null) return;
    // Push to the call stack when the function starts
    stk.push(root);
    traverse(root.left);
    traverse(root.right);
    // Leave the call stack when the function ends
    stk.pop();
}

If nodes are pushed onto the stack during the pre-order traversal and popped during the post-order traversal, the changes in the stk reflect the recursive process of the traverse function (in the GIF, green nodes are those pushed onto the stack, and gray nodes are those popped from the stack):

In simple terms, the process is as follows:

1. When you get a node, traverse left continuously (because traverse(root.left) comes first), and push all the nodes you encounter onto the stack.

2. Once you reach the end on the left, start popping from the stack. Check the right pointer of the top node; if it's not null, repeat step 1.

The iterative code looks like this:

java 🟢

class Solution {
    private Stack<TreeNode> stk = new Stack<>();

    public List<Integer> traverse(TreeNode root) {
        pushLeftBranch(root);
        
        while (!stk.isEmpty()) {
            TreeNode p = stk.pop();
            pushLeftBranch(p.right);
        }
    }

    // Push all the nodes in the left branch to the stack
    private void pushLeftBranch(TreeNode p) {
        while (p != null) {
            stk.push(p);
            p = p.left;
        }
    }
}

cpp 🤖

class Solution {
private:
    stack<TreeNode*> stk;

public:
    vector<int> traverse(TreeNode* root) {
        pushLeftBranch(root);
        
        while (!stk.empty()) {
            TreeNode* p = stk.top();
            stk.pop();
            pushLeftBranch(p->right);
        }
    }

    // Push the left branch all the way down into the stack
    void pushLeftBranch(TreeNode* p) {
        while (p != nullptr) {
            stk.push(p);
            p = p->left;
        }
    }
};

python 🤖

class Solution:
    def __init__(self):
        # initialize a stack
        self.stk = []

    def traverse(self, root: TreeNode) -> List[int]:
        # traverse the left branch
        self.pushLeftBranch(root)

        # while the stack is not empty, perform loop operations
        while self.stk:
            # pop the top element of the stack, which is the leftmost child node
            p = self.stk.pop()
            # traverse the left branch of the right subtree of the node
            self.pushLeftBranch(p.right)

    # push all the left branch nodes into the stack
    def pushLeftBranch(self, p: TreeNode) -> None:
        while p:
            self.stk.append(p)
            p = p.left

go 🤖

func traverse(root *TreeNode) []int {
    stk := stack.New()
    pushLeftBranch(stk, root)
    res := make([]int, 0)

    // constantly push the left branch into the stack, and when popping the node, try to push the right branch into the stack
    for stk.Len() != 0 {
        p := stk.Pop().(*TreeNode)
        res = append(res, p.Val)
        pushLeftBranch(stk, p.Right)
    }

    return res
}

// push the left branch into the stack, continuously looking for the left node of p
func pushLeftBranch(stk *stack.Stack, p *TreeNode) {
    for p != nil {
        stk.Push(p)
        p = p.Left
    }
}

javascript 🤖

var traverse = function(root) {
    const stk = [];

    pushLeftBranch(root);
        
    while (stk.length) {
        const p = stk.pop();
        pushLeftBranch(p.right);
    }

    // Push all the left branches to the bottom into the stack
    function pushLeftBranch(p) {
        while (p) {
            stk.push(p);
            p = p.left;
        }
    }
};

Although the above code can simulate the execution process of a recursive function, it has not yet identified the positions of pre-order, in-order, and post-order code within the recursive code. Therefore, further modifications are needed.

Iterative Code Framework

Where is the key to reflecting pre-order, in-order, and post-order traversal in iterative code?

When I take a node p out of the stack, I should figure out the traversal status of the left and right subtrees of this node p.

• If neither the left nor the right subtree of p has been traversed, then operating on p now belongs to the pre-order traversal code.
• If the left subtree of p has been traversed, but the right subtree has not, then operating on p now belongs to the in-order traversal code.
• If both the left and right subtrees of p have been traversed, then operating on p now belongs to the post-order traversal code.

The above logic can be written in pseudocode as follows:

java 🟢

class Solution {
    private Stack<TreeNode> stk = new Stack<>();

    public List<Integer> traverse(TreeNode root) {
        pushLeftBranch(root);
        
        while (!stk.isEmpty()) {
            TreeNode p = stk.peek();
            
            if (p 的左子树被遍历完了) {
                // *****************
                // * Position of the inorder traversal code *
                // *****************
                pushLeftBranch(p.right);
                // Traverse the right subtree of p
            }

            if (p 的右子树被遍历完了) {
                // *****************
                // * Position of the postorder traversal code *
                // *****************
                stk.pop();
                // The tree with p as the root has been traversed, pop the stack
            }
        }
    }

    private void pushLeftBranch(TreeNode p) {
        while (p != null) {
            // *****************
            // * Position of the preorder traversal code *
            // *****************
            stk.push(p);
            p = p.left;
        }
    }
}

cpp 🤖

class Solution {
private:
    stack<TreeNode*> stk;

public:
    vector<int> traverse(TreeNode* root) {
        pushLeftBranch(root);

        vector<int> result;
        
        while (!stk.empty()) {
            TreeNode* p = stk.top();
            
            if (p->left == nullptr) {
                // *****************
                // * position of inorder traversal code *
                // *****************
                // traverse the right subtree of p
                stk.pop();
                pushLeftBranch(p->right);
            }
            else if (p->right == nullptr) {
                // *****************
                // * position of postorder traversal code *
                // *****************
                // the tree with p as the root has been traversed, pop the stack
                stk.pop();
                result.push_back(p->val);
            }
            else {
                stk.pop();
                stk.push(p);
                pushLeftBranch(p->right);
                pushLeftBranch(p->left);
            }
        }

        return result;
    }

    void pushLeftBranch(TreeNode* p) {
        while (p != nullptr) {
            // *****************
            // * position of preorder traversal code *
            // *****************
            stk.push(p);
            p = p->left;
        }
    }
};

python 🤖

class Solution:
    def __init__(self):
        self.stk = []

    def traverse(self, root: TreeNode) -> List[int]:
        self.pushLeftBranch(root)
        
        while self.stk:
            p = self.stk[-1]
            
            if p.左子树被遍历完了:
                // *****************
                // * 中序遍历代码位置 *
                // *****************
                self.pushLeftBranch(p.right)

            if p.右子树被遍历完了:
                // *****************
                // * 后序遍历代码位置 *
                // *****************
                self.stk.pop()

    def pushLeftBranch(self, p: TreeNode) -> None:
        while p:
            // *****************
            // * 前序遍历代码位置 *
            // *****************
            self.stk.append(p)
            p = p.left

go 🤖

func traverse(root *TreeNode) []int {
    var stk []*TreeNode
    pushLeftBranch(&stk, root)
    var result []int

    for len(stk) != 0 {
        p := stk[len(stk)-1]
        if p.Left == nil {
            // *****************
            // * position of inorder traversal code *
            // *****************
            result = append(result, p.Val)
            stk = stk[:len(stk)-1]
            if p.Right != nil {
                pushLeftBranch(&stk, p.Right)
            }
        } else if root == p.Left {
            // *****************
            // * position of preorder traversal code *
            // *****************
            result = append(result, p.Val)
            if p.Right != nil {
                pushLeftBranch(&stk, p.Right)
            }
        } else {
            // *****************
            // * position of postorder traversal code *
            // *****************
            stk = stk[:len(stk)-1]
            result = append(result, p.Val)
        }
    }
    return result
}

func pushLeftBranch(stk *[]*TreeNode, p *TreeNode) {
    for p != nil {
        (*stk) = append((*stk), p)
        p = p.Left
    }
}

javascript 🤖

var traverse = function(root) {
    var stk = [];
    pushLeftBranch(root);
        
    while (stk.length > 0) {
        var p = stk[stk.length - 1];
            
        if (p.的左子树被遍历完了) {
            // *****************
            // * the position of inorder traversal code *
            // *****************
            // traverse the right subtree of p
            pushLeftBranch(p.right);
        }

        if (p.的右子树被遍历完了) {
            // *****************
            // * the position of postorder traversal code *
            // *****************
            // the tree with root p has been traversed, pop from stack
            stk.pop();
        }
    }

    function pushLeftBranch(p) {
        while (p !== null) {
            // *****************
            // * the position of preorder traversal code *
            // *****************
            stk.push(p); 
            p = p.left;
        }
    }
};

With the previous explanation, this code should be easy to understand. The key question is: how do we determine whether the left and right subtrees of p have been traversed?

It's actually quite simple. We just need to maintain a visited pointer, which points to the "last completed root node." This allows us to determine the traversal status of p's left and right subtrees.

Here is the complete code framework for iterative traversal of a binary tree:

java 🟢

class Solution {
    // simulate function call stack
    private Stack<TreeNode> stk = new Stack<>();

    // traverse the left branch all the way down
    private void pushLeftBranch(TreeNode p) {
        while (p != null) {
            // *****************
            // * position of preorder traversal code *
            // *****************
            stk.push(p);
            p = p.left;
        }
    }

    public List<Integer> traverse(TreeNode root) {
        // point to the root node of the last traversed subtree
        TreeNode visited = new TreeNode(-1);
        // start traversing the whole tree
        pushLeftBranch(root);
        
        while (!stk.isEmpty()) {
            TreeNode p = stk.peek();
            
            // p's left subtree has been traversed, and the right subtree has not been traversed
            if ((p.left == null || p.left == visited) 
            && p.right != visited) {
                // *****************
                // * position of inorder traversal code *
                // *****************
                // go traverse p's right subtree
                pushLeftBranch(p.right);
            }
            // p's right subtree has been traversed
            if (p.right == null || p.right == visited) {
                // *****************
                // * position of postorder traversal code *
                // *****************
                // the subtree rooted at p has been traversed, pop from the stack
                // the visited pointer points to p
                visited = stk.pop();
            }
        }
    }
}

cpp 🤖

class Solution {
private:
    // simulate function call stack
    stack<TreeNode*> stk;
    
    // traverse the left branch all the way down
    void pushLeftBranch(TreeNode* p) {
        while (p != nullptr) {
            // *****************
            // * position of preorder traversal code *
            // *****************
            stk.push(p);
            p = p->left;
        }
    }

public:
    vector<int> traverse(TreeNode* root) {
        // point to the root node of the last traversed subtree
        TreeNode* visited = new TreeNode(-1);
        // start traversing the whole tree
        pushLeftBranch(root);
        
        while (!stk.empty()) {
            TreeNode* p = stk.top();
            
            // p's left subtree has been traversed, and the right subtree has not been traversed
            if ((p->left == nullptr || p->left == visited) 
            && p->right != visited) {
                // *****************
                // * position of inorder traversal code *
                // *****************
                // go traverse p's right subtree
                pushLeftBranch(p->right);
            }
            // p's right subtree has been traversed
            if (p->right == nullptr || p->right == visited) {
                // *****************
                // * position of postorder traversal code *
                // *****************
                // the subtree rooted at p has been traversed, pop from the stack
                // visited pointer points to p
                visited = p;
                stk.pop();
            }
        }
    }
};

python 🤖

class Solution:
    def __init__(self):
        # simulate the function call stack
        self.stk = []
        
    # traverse the left branch all the way down
    def pushLeftBranch(self, p):
        while p:
            # the position of preorder traversal code
            self.stk.append(p)
            p = p.left
    
    def traverse(self, root: TreeNode) -> List[int]:
        # point to the root node of the last traversed subtree
        visited = TreeNode(-1)
        # start traversing the whole tree
        self.pushLeftBranch(root)
        
        res = []
        while self.stk:
            p = self.stk[-1]
            
            # p's left subtree has been traversed, and the right subtree has not been traversed
            if (not p.left or p.left == visited) and (not p.right or p.right != visited):
                # the position of inorder traversal code
                res.append(p.val)
                # go traverse p's right subtree
                self.pushLeftBranch(p.right)
            
            # p's right subtree has been traversed
            if not p.right or p.right == visited:
                # the position of postorder traversal code
                # the subtree rooted at p has been traversed, pop from the stack
                # the visited pointer points to p
                visited = self.stk.pop()
        
        return res

go 🤖

type Stack struct {
    data []*TreeNode
}

func (s *Stack) Push(x *TreeNode) {
    s.data = append(s.data, x)
}

func (s *Stack) Pop() *TreeNode {
    if len(s.data) == 0 {
        return nil
    }
    x := s.data[len(s.data)-1]
    s.data = s.data[:len(s.data)-1]
    return x
}

func (s *Stack) Peek() *TreeNode {
    if len(s.data) == 0 {
        return nil
    }
    return s.data[len(s.data)-1]
}

func traverse(root *TreeNode) []int {
    var res []int
    stk := new(Stack)
    visited := &TreeNode{Val: -1}
    // start traversing the whole tree
    pushLeftBranch(stk, root)
    for !isEmpty(stk) {
        p := peek(stk)
        if (p.Left == nil || p.Left == visited) && p.Right != visited {
            // position of inorder traversal code
            pushLeftBranch(stk, p.Right)
        }
        if p.Right == nil || p.Right == visited {
            // position of postorder traversal code
            visited = pop(stk)
            res = append(res, visited.Val)
        }
    }
    return res
}

func pushLeftBranch(stk *Stack, p *TreeNode) {
    for p != nil {
        // position of preorder traversal code
        stk.Push(p)
        p = p.Left
    }
}

func peek(stk *Stack) *TreeNode {
    return stk.Peek()
}

func pop(stk *Stack) *TreeNode {
    return stk.Pop()
}

func isEmpty(stk *Stack) bool {
    return len(stk.data) == 0
}

javascript 🤖

var traverse = function(root) {
    var stk = new Stack();
    
    var pushLeftBranch = function(p) {
        while (p != null) {
            // *****************
            // * position of preorder traversal code *
            // *****************
            stk.push(p);
            p = p.left;
        }
    };
    
    // points to the root of the subtree last traversed
    var visited = new TreeNode(-1);
    // start traversing the whole tree
    pushLeftBranch(root);
    
    while (!stk.isEmpty()) {
        var p = stk.peek();
        
        // p's left subtree has been traversed, and the right subtree has not been traversed
        if ((p.left == null || p.left == visited) 
        && p.right != visited) {
            // *****************
            // * position of inorder traversal code *
            // *****************
            // go traverse p's right subtree
            pushLeftBranch(p.right);
        }
        // p's right subtree has been traversed
        if (p.right == null || p.right == visited) {
            // *****************
            // * position of postorder traversal code *
            // *****************
            // the subtree rooted at p has been traversed, pop from the stack
            // the visited pointer points to p
            visited = stk.pop();
        }
    }
};

The most skillful part of the code is the visited pointer, which records the root node of the most recently traversed subtree (the node most recently popped from the stack). We can determine whether the left and right subtrees of node p have been traversed by comparing p's left and right pointers with visited. This allows us to separate the code positions for pre-order, in-order, and post-order traversals.

提示

The visited pointer is initialized to point to a newly created binary tree node, acting as a special value to avoid duplication with nodes in the input binary tree.

By simply copying and pasting the code from the pre-order, in-order, and post-order positions of a recursive algorithm into the corresponding positions in the above framework, you can convert any recursive binary tree algorithm into an iterative form.

For example, if you are asked to return the result of a post-order traversal of a binary tree, you can write it like this:

java 🟢

class Solution {
    private Stack<TreeNode> stk = new Stack<>();

    public List<Integer> postorderTraversal(TreeNode root) {
        // record the result of postorder traversal
        List<Integer> postorder = new ArrayList<>();
        TreeNode visited = new TreeNode(-1);

        pushLeftBranch(root);
        while (!stk.isEmpty()) {
            TreeNode p = stk.peek();

            if ((p.left == null || p.left == visited) 
            && p.right != visited) {
                pushLeftBranch(p.right);
            }

            if (p.right == null || p.right == visited) {
                // the position of postorder traversal code
                postorder.add(p.val);
                visited = stk.pop();
            }
        }

        return postorder;
    }

    private void pushLeftBranch(TreeNode p) {
        while (p != null) {
            stk.push(p);
            p = p.left;
        }
    }
}

cpp 🤖

class Solution {
private:
    stack<TreeNode*> stk;

public:
    vector<int> postorderTraversal(TreeNode* root) {
        // record the result of postorder traversal
        vector<int> postorder;
        TreeNode* visited = new TreeNode(-1);

        pushLeftBranch(root);
        while (!stk.empty()) {
            TreeNode* p = stk.top();

            if ((p->left == nullptr || p->left == visited)
                && p->right != visited) {
                pushLeftBranch(p->right);
            }

            if (p->right == nullptr || p->right == visited) {
                // the position of the postorder traversal code
                postorder.push_back(p->val);
                visited = stk.top();
                stk.pop();
            }
        }

        return postorder;
    }

private:
    void pushLeftBranch(TreeNode* p) {
        while (p != nullptr) {
            stk.push(p);
            p = p->left;
        }
    }
};

python 🤖

class Solution:
    def __init__(self):
        self.stk = []
        
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        # record the result of postorder traversal
        postorder = []
        visited = TreeNode(-1)
        
        self.pushLeftBranch(root)
        
        while len(self.stk) != 0:
            p = self.stk[-1]
            
            if (p.left == None or p.left == visited) and p.right != visited:
                self.pushLeftBranch(p.right)
                
            if p.right == None or p.right == visited:
                # postorder traversal code position
                postorder.append(p.val)
                visited = self.stk.pop()
                
        return postorder
    
    def pushLeftBranch(self, p):
        while p != None:
            self.stk.append(p)
            p = p.left

go 🤖

// Iterative writing
func postorderTraversal(root *TreeNode) []int {
    stk := []*TreeNode{}
    postorder := []int{}
    visited := &TreeNode{Val: -1}

    // push the left subtree node first
    pushLeftBranch(root, &stk)
    for len(stk) > 0 {
        p := stk[len(stk) - 1]
        if (p.Left == nil || p.Left == visited) && p.Right != visited {
            // if the left subtree is not empty and it has not been visited, push the left node of the right subtree
            pushLeftBranch(p.Right, &stk)
        }

        if p.Right == nil || p.Right == visited {
            // if both left and right subtrees have been visited, it means this node should be added to the postorder traversal collection
            postorder = append(postorder, p.Val)
            visited = stk[len(stk) - 1]
            stk = stk[:len(stk) - 1]
        }
    }
    return postorder
}

func pushLeftBranch(node *TreeNode, stk *[]*TreeNode) {
    for node != nil {
        *stk = append(*stk, node)
        node = node.Left
    }
}

javascript 🤖

var postorderTraversal = function(root) {
    // create a stack for traversing nodes
    const stk = [];
    // create a list to record the postorder traversal results
    const postorder = [];

    // define a marker node
    let visited = new TreeNode(-1);
    // push the left branch into the stack one by one
    pushLeftBranch(root);

    while (stk.length > 0) {
        // get the top node of the stack
        let node = stk[stk.length - 1];
        if ((node.left === null || node.left === visited) && (node.right !== visited)) {
            // if the left subtree of the current node has been traversed and the right subtree has not been traversed, traverse the right subtree
            pushLeftBranch(node.right);
        }

        if ((node.right === null || node.right === visited)) {
            // the right subtree of the current node has been traversed, and the current node is about to pop
            postorder.push(node.val);
            visited = stk.pop();
        }
    }

    // traverse to the left, pushing the left branch nodes into the stack
    function pushLeftBranch(node) {
        while (node !== null) {
            stk.push(node);
            node = node.left;
        }
    }

    return postorder;
};

Of course, for any binary tree algorithm, if you want to convert recursion to iteration, you can use this framework. Just map the pre-order, in-order, and post-order positions of the recursive code accordingly.

The iterative solution is done here. However, I still want to emphasize that, except for BFS level-order traversal, binary tree problems are best solved using recursion, as recursion aligns perfectly with the structural characteristics of binary trees.

Ultimately, this iterative solution is just using a stack to simulate recursive calls. So, comparing it with the recursive solution should make it easier to understand and remember.

This article concludes here. For more classic binary tree exercises and training in recursive thinking, please refer to the Recursive Special Practice section in the binary tree chapter.

---

引用本文的题目

安装 我的 Chrome 刷题插件 点开下列题目可直接查看解题思路：

LeetCode	力扣
173. Binary Search Tree Iterator	173. 二叉搜索树迭代器
872. Leaf-Similar Trees	872. 叶子相似的树
-	剑指 Offer II 055. 二叉搜索树迭代器

---