题解 | #实现二叉树先序，中序和后序遍历#

import java.util.*;

/*

• public class TreeNode {
• int val = 0;
• TreeNode left = null;
• TreeNode right = null;
• } */

public class Solution { /** * * @param root TreeNode类 the root of binary tree * @return int整型二维数组 */ public int[][] threeOrders (TreeNode root) { int[] preorder = this.preOrder(root); int n = preorder.length;

    int[][] result = new int[3][n];
    result[0] = preorder;
    result[1] = this.inOrder(root);
    result[2] = this.postOrder(root);
    return result;
}

public int[] preOrder(TreeNode root){
    if (root == null || root.equals("#")){
        return new int[0];
    }
    List<TreeNode> toBeTraversed = new ArrayList<>();
    toBeTraversed.add(root);
    TreeNode currentNode;
    List<Integer> result = new ArrayList<>();
    while(toBeTraversed.size() > 0){
        currentNode = toBeTraversed.get(0);
        result.add(currentNode.val);
        int index = 0;
        toBeTraversed.remove(0);
        if (currentNode.left != null && !currentNode.left.equals("#")){
            toBeTraversed.add(index, currentNode.left);
            index += 1;
        }
        if (currentNode.right != null && !currentNode.right.equals("#")){
            toBeTraversed.add(index, currentNode.right);
        }
    }
    int[] resultArray = result.stream().mapToInt(Integer::valueOf).toArray();
    return resultArray;
}

public int[] inOrder(TreeNode root){
    if (root == null || root.equals("#")){
        return new int[0];
    }
    List<TreeNode> alreadyTraversed = new ArrayList<>();
    List<TreeNode> toBeTraversed = new ArrayList<>();
    toBeTraversed.add(root);
    TreeNode currentNode;
    List<Integer> result = new ArrayList<>();
    while(toBeTraversed.size() > 0){
        currentNode = toBeTraversed.get(0);
        int index = 0;
        if (alreadyTraversed.contains(currentNode)){
            result.add(currentNode.val);
            toBeTraversed.remove(0);
            continue;
        }
        if (currentNode.left != null && !currentNode.left.equals("#")){
            toBeTraversed.add(index, currentNode.left);
            index += 2;
        }else{
            result.add(currentNode.val);
            toBeTraversed.remove(0);
        }
        if (currentNode.right != null && !currentNode.right.equals("#")){
            toBeTraversed.add(index, currentNode.right);
        }
        alreadyTraversed.add(currentNode);
    }
    int[] resultArray = result.stream().mapToInt(Integer::valueOf).toArray();
    return resultArray;
}

public int[] postOrder(TreeNode root){
    if (root == null || root.equals("#")){
        return new int[0];
    }
    List<TreeNode> alreadyTraversed = new ArrayList<>();
    List<TreeNode> toBeTraversed = new ArrayList<>();
    toBeTraversed.add(root);
    TreeNode currentNode;
    List<Integer> result = new ArrayList<>();
    while(toBeTraversed.size() > 0){
        currentNode = toBeTraversed.get(0);
        int index = 0;
        int count = 0;
        if (alreadyTraversed.contains(currentNode)){
            result.add(currentNode.val);
            toBeTraversed.remove(0);
            continue;
        }
        if (currentNode.left != null && !currentNode.left.equals("#")){
            toBeTraversed.add(index, currentNode.left);
            index += 1;
            count += 1;
        }
        if (currentNode.right != null && !currentNode.right.equals("#")){
            toBeTraversed.add(index, currentNode.right);
            count += 1;
        }
        if (count == 0){
            result.add(currentNode.val);
            toBeTraversed.remove(0);
        }
        alreadyTraversed.add(currentNode);
    }
    int[] resultArray = result.stream().mapToInt(Integer::valueOf).toArray();
    return resultArray;
}

}