flyingchase

非递归遍历二叉树

递归本质上就是栈 由于二叉树提供节点只能向下访问 无法返回 故而使用栈结构实现返回

public static List<Integer> inOrderTraversalBT(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    //空树则直接返回null的res
    if (root == null) {
        return res;
    }
    Stack<TreeNode> stack = new Stack<>();
    // 保存root
    TreeNode cur = root;
    while (cur != null || !stack.isEmpty()) {
        // 向树的最左侧走 并不断压栈
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
        // 走完最左侧后弹栈顶
        TreeNode node = stack.pop();
        res.add(node.val);
        // 往上层的右边去再重复找最左侧
        cur = node.right;
    }
    return res;
}


public static List<Integer> preOrderTraversalBT(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    //空树则直接返回null的res
    if (root == null) {
        return res;
    }
    Stack<TreeNode> stack = new Stack<>();
    // 保存root
    TreeNode cur = root;
    while (cur != null || !stack.isEmpty()) {
        // 向树的最左侧走 并不断压栈入数组
        while (cur != null) {
            res.add(cur.val);
            stack.push(cur);
            cur = cur.left;
        }
        // 走完最左侧后弹栈顶 无须入组 cur循环内已经入组
        TreeNode node = stack.pop();
        // 往上层的右边去 再重复找最左侧
        cur = node.right;
    }

    return res;
}


public static List<Integer> postOrderTraversalBT(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    //空树则直接返回null的res
    if (root == null) {
        return res;
    }
    Stack<TreeNode> stack = new Stack<>();
    // 保存root
    TreeNode cur = root;
    while (cur != null || !stack.isEmpty()) {
        // 向树的最右侧走 并不断压栈入数组
        while (cur != null) {
            res.add(cur.val);
            stack.push(cur);
            cur = cur.right; // 使得reverse后正常左在前
        }
        // 走完最右侧后弹栈顶 无须入组 cur循环内已经入组
        TreeNode node = stack.pop();
        // 往上层的左边去 再重复找最右侧
        cur=node.left;
    }
    Collections.reverse(res);
    return res;
}