讨论/《深度优先搜索》 - 例题:二叉树的后序遍历/
《深度优先搜索》 - 例题:二叉树的后序遍历
共 4 个回复

JavaScript 后序遍历

/**
 * 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) {
    const res = [];

    const dfs = (treeNode) => {
        if(treeNode === null){
            return;
        }
        dfs(treeNode.left);
        dfs(treeNode.right);
        res.push(treeNode.val)
    }

    dfs(root);

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

        List<TreeNode> stack = new ArrayList<>();
        List<TreeNode> left = new ArrayList<>();

        while (root != null || !left.isEmpty()) {
            while (root != null) {     
                stack.add(root);
                if (root.left != null) {
                   left.add(root.left);
                }
                root = root.right;
            }

            if (!left.isEmpty()) {
                root = left.remove(left.size() - 1);
            }
        }

        while (!stack.isEmpty()) {
            postorder.add(stack.remove(stack.size() - 1).val);
        }
        return postorder;
    }
}
class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        if not root : return []
        q = deque([root])
        res = []
        while q:
            cur = q.pop()
            res.append(cur.val)
            if cur.left : q.append(cur.left)
            if cur.right : q.append(cur.right)
        return res[::-1]
class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        stack = []
        # 后序,相同模板
        while stack or root:
            while root:
                stack.append(root)
                res.append(root.val)
                root = root.right
            root = stack.pop()
            root = root.left
        return res[::-1]