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

/*
 * 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整型一维数组
     */
    List<Integer> list = new ArrayList<>();
    public int[] postorderTraversal (TreeNode root) {
        // write code here
        TreeNode node = root;
        
        //常规非递归
//          Stack<TreeNode> stack = new Stack<>();
//          TreeNode pre = null;
//         while(node != null || !stack.isEmpty()){
//             while(node != null){
//                 stack.push(node);
//                 node = node.left;
//             }
//             node = stack.pop();
//             if(node.right == null || node.right == pre){
//                 list.add(node.val);
//                 pre = node;
//                 node = null;
//             }else{
//                 stack.push(node);
//                 node = node.right;
//             }
//         }
       //morris遍历
         while(node != null){
            if(node.left != null){
                TreeNode cur = node.left;
                while(cur.right != null && cur.right != node){
                    cur = cur.right;
                }
                if(cur.right != node){
                    cur.right = node;
                    node = node.left;
                }else{
                    cur.right = null;
                    postMorris(node.left);  
                    node = node.right;
                }
            } else{
                postMorris(node.left);
             node = node.right;
            }
             
        }
        postMorris(root);   
        int[] arrays = new int[list.size()];
        int i = 0;
        for(int l : list){
            arrays[i++] = l;
        }
        return arrays;       
    }
    public void postMorris(TreeNode root){
        TreeNode node = reverseList(root);
        TreeNode cur = node;
        while(cur != null){
            list.add(cur.val);
            cur = cur.right;
        }
        reverseList(node);
    }
    public TreeNode reverseList(TreeNode root){
        TreeNode cur = root;
        TreeNode pre = null;
        while(cur != null){
            TreeNode node = cur.right;
            cur.right = pre;
            pre = cur;
            cur = node;
        }
        return pre;
    }

 



}