题解 | #二叉树的后序遍历#

二叉树的后序遍历

http://www.nowcoder.com/practice/1291064f4d5d4bdeaefbf0dd47d78541

本题主要信息

1、给定一个二叉树，返回他的后序遍历的序列。

2、后序遍历是值按照左节点->右节点->根节点的顺序的遍历。

方法一：递归

具体方法

按照访问左子树——右子树——根节点的方式遍历这棵树，而在访问左子树或者右子树的时候，我们按照同样的方式遍历，直到遍历完整棵树。因此整个遍历过程天然具有递归的性质，我们可以直接用递归函数来模拟这一过程。

定义 postorder(root) 表示当前遍历到 root 节点的答案。按照定义，我们只要递归调用 postorder(root->left) 来遍历 root 节点的左子树，然后递归调用 postorder(root->right) 来遍历 root 节点的右子树，最后将 root 节点的值加入答案即可，递归终止的条件为碰到空节点。

Java代码

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型一维数组
     */
    ArrayList<Integer> temp = new ArrayList<>();
    public int[] postorderTraversal (TreeNode root) {
        // write code here

            search(root);
            int []result = new int[temp.size()];
            // 存入到int数组中
            for(int i=0;i<temp.size();i++)
                result[i] = temp.get(i);
        return result;
    }
  // 后续遍历
    public void search(TreeNode root){
        if(root == null)
            return;
      
        search(root.left);
        search(root.right);
        temp.add(root.val);
    }
}

复杂度分析

时间复杂度： $O (n)$ ，其中 $n$ 是二叉搜索树的节点数。每一个节点恰好被遍历一次。
空间复杂度： $O (n)$ ，为递归过程中栈的开销，平均情况下为 $O (l o g n)$ ，最坏情况下树呈现链状，为 $O (n)$ 。

方法二：非递归

具体方法

后序非递归遍历顺序：左右根
用堆栈来存储结点时，必须分清返回根节点时是从左子树返回还是右子树返回。
所以使用辅助指针r，指向最近访问过的结点。
也可在结点中增加一个标志域，记录是否已被访问过。

Java代码

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型一维数组
     */
    
    public int[] postorderTraversal (TreeNode root) {
        // write code here
            List<Integer> temp = search(root);
            int []result = new int[temp.size()];
            
            for(int i=0;i<temp.size();i++)
                result[i] = temp.get(i);
        return result;
    }
    // 非递归遍历
        public List<Integer> search(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;
            }
        }
        return res;
    }
}