145. Binary Tree Postorder Traversal

一、题目

　　1、审题

　　

　　2、给出一棵二叉树，采用迭代输出其后序遍历序列值。

二、解答

　　1、思路：

　　　　方法一、

　　　　　　采用一个 Stack 记录节点，一个指针 pre 指示 right 节点是否访问过。

    public List<Integer> postorderTraversal(TreeNode root) {
        
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode pre = null;    // 用于记录 right 节点是否访问过
        TreeNode node;
        
        while(root != null || !stack.isEmpty()) {
            
            while(root != null) {
                stack.push(root);
                root = root.left;
            }
            
            if(!stack.isEmpty()) {
                node = stack.peek();    // node 的 left 已经访问了的。
                
                // node 的 right 存在且未访问过
                if(node.right != null && node.right != pre) 
                    root = node.right;
                
                // node 的 right 不存在或者已经访问过
                else {
                    stack.pop();
                    pre = node;
                    list.add(node.val);
                }
            }
        }
        return list;
    }

　　方法二、

　　　　①、伪前序遍历比较好写： 根 ---> 右 ---> 左；

　　　　②、后续遍历 ： 左 ---> 右 ---> 根 ， 即为 ① 的逆序。

    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root == null)
            return list;
        Stack<TreeNode> stack = new Stack<>();
        stack.add(root);
        
        while(!stack.isEmpty()) {
            
            root = stack.pop();
            list.add(root.val);
            
            if(root.left != null)
                stack.add(root.left);
            
            if(root.right != null)
                stack.add(root.right);
        }
        
        Collections.reverse(list);
        return list;
    }

　　　方法三、

　　　　Morris Traversal 方法线索二叉树，只需要O(1)空间，而且同样可以在O(n)时间内完成。

　　　　从下向上，将每一条右斜树节点全部逆序输出。

    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root == null)
            return list;
        TreeNode dump = new TreeNode(0);
        dump.left = root;
        
        TreeNode cur = dump;
        TreeNode pre = null;
        
        while(cur != null) {
            
            if(cur.left == null) { 
                cur = cur.right;
            }
            else {
                
                pre = cur.left;
                while(pre.right != null && pre.right != cur)
                    pre = pre.right;
                
                if(pre.right == null) {
                    pre.right = cur;
                    cur = cur.left;
                }
                else {
                    // 将线索的一条右斜支链逆序输出
                    addNodeToList(list, cur.left, pre);
                    pre.right = null;
                    cur = cur.right;
                }
            }
        }
        return list;
    }
    private void addNodeToList(List<Integer> list, TreeNode startNode, TreeNode endNode) {
        reverse(startNode, endNode);
        TreeNode node = endNode;
        while(true) {
            list.add(node.val);
            if(node == startNode)
                break;
            node = node.right;
        }
        reverse(endNode, startNode);
    }

    private void reverse(TreeNode startNode, TreeNode endNode) {
        if(startNode == endNode)
            return;
        
        TreeNode x = startNode;
        TreeNode y = x.right;
        
        while(true) {
            TreeNode next = y.right;
            y.right = x;
            x = y;
            y = next;
            if(x == endNode)
                break;
        }
    }