145. Binary Tree Postorder Traversal

题目:

Given a binary tree, return the postorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},

   1
    
     2
    /
   3

return [3,2,1].

Note: Recursive solution is trivial, could you do it iteratively?

链接: http://leetcode.com/problems/binary-tree-postorder-traversal/

题解:

二叉树后序遍历。 刚接触leetcode时也做过这道题,用了很蠢笨的方法。现在学习discuss里大神们的版本,真的进步很多。下面这个版本是基于上道题目 - 二叉树先序遍历的。由于后序遍历是left -> right -> root,  先序是root -> left -> right, 所以我们改变的只是如何插入结果到 list里,以及被压入栈的先后顺序而已。在这里,pop出的结果要插入到list前部,而且要先把左子树压入栈,其次是右子树。

Time Complexity - O(n),Space Complexity - O(n)。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new LinkedList<>();
        if(root == null)
            return res;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        
        while(!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if(node != null) {
                res.add(0, node.val);           // insert at the front of list
                stack.push(node.left);          // opposite push
                stack.push(node.right);
            }
        }
        
        return res;
    }
}

二刷:

Java:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new LinkedList<>();
        if (root == null) return res;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if (node != null) {
                res.add(0, node.val);
                stack.push(node.left);
                stack.push(node.right);
            }
        }
        return res;
    }
}

Recursive:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        postorderTraversal(res, root);
        return res;
    }
    
    private void postorderTraversal(List<Integer> res, TreeNode root) {
        if (root == null) return;
        postorderTraversal(res, root.left);
        postorderTraversal(res, root.right);
        res.add(root.val);
    }
}

三刷:

Java:

Reversed preorder traversal with LinkedList and Stack:

主要使用一个LinkedList和一个stack来辅助我们的遍历。其实顺序和pre-order并没有区别,只是把遍历过的节点值不断从链表头部插入,也就形成了我们的后续遍历。注意处理节点的左节点和右节点时,对栈先压入左节点再压入右节点,之后pop时我们就会先处理右节点。

Time Complexity - O(n),Space Complexity - O(n)。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new LinkedList<>();
        if (root == null) return res;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode node = root;
        stack.push(node);
        while (!stack.isEmpty()) {
            node = stack.pop();
            res.add(0, node.val);
            if (node.left != null) stack.push(node.left);
            if (node.right != null) stack.push(node.right);
        }
        return res;
    }
}

Recursive:

Time Complexity - O(n),Space Complexity - O(n)。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        postorderTraversal(res, root);
        return res;
    }
    
    private void postorderTraversal(List<Integer> res, TreeNode root) {
        if (root == null) return;
        postorderTraversal(res, root.left);
        postorderTraversal(res, root.right);
        res.add(root.val);
    }
}

Morris Traversal:

三刷终于学习了Morris Traversal。这里的Morris Traversal也使用的是Reversed Preorder traversal with LinkedList。也就是使用类似与Preorder traversal类似的代码,以及一个LinkedList,每次从表头插入结果。

因为Postorder和Preorder的对应关系,这里与Preorder Morris Traversal不同的就是,我们要找的不是左子树的predecessor,而是右子树中当前节点的successor,也就是当前节点右子树中最左边的元素。下面我们详述一下步骤。

  1. 依然先做一个root的reference - node,在node非空的情况对树进行遍历。当node.right为空的时候,我们将node.val从链表res头部插入,然后向左遍历左子树
  2. 假如右子树非空,则我们要找到当前节点在右子树中的succesor,简称succ,一样是两种情况:
    1. 首次访问succ,此时succ.left = null,我们把succ和当前node连接起来,进行succ.left = node。之后讲node.val从链表res头部插入,向右遍历node.right
    2. 否则,我们二次访问succ,这时succ.left = node,我们做一个还原操作,设succ.left = null,然后向左遍历node.left。因为node.val已经处理过,所以不要重复处理node.val.

Time Complexity - O(n),Space Complexity - O(1)。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new LinkedList<>();
        TreeNode node = root, succ = null;
        while (node != null) {
            if (node.right == null) {
                res.add(0, node.val);
                node = node.left;
            } else {
                succ = node.right;
                while (succ.left != null && succ.left != node) {
                    succ = succ.left;
                }
                if (succ.left == null) {
                    succ.left = node;
                    res.add(0, node.val);
                    node = node.right;
                } else {
                    succ.left = null;
                    node = node.left;
                }
            }
        }
        return res;
    }
}

Reference:

144. Binary Tree Preorder Traversal

https://leetcode.com/discuss/9736/accepted-code-with-explaination-does-anyone-have-better-idea

https://leetcode.com/discuss/71943/preorder-inorder-and-postorder-iteratively-summarization

https://leetcode.com/discuss/21995/a-very-concise-solution

https://leetcode.com/discuss/36711/solutions-iterative-recursive-traversal-different-solutions

原文地址:https://www.cnblogs.com/yrbbest/p/4489571.html