二叉树知识

先序遍历：根节点 - 左节点 - 右节点
根据上面的图： 1 - 2 - 5 - 3 - 4

中序遍历：左节点 - 根节点 - 右节点
根据上面的图：5 - 2 - 3 - 1 - 4

后序遍历：左节点 - 右节点 - 根节点
根据上面的图：5 - 3 - 2 - 4 - 1

解题思路

递归

这个就很简单了，递归的去处理一下就可以，一会直接看代码就可以了。

迭代

迭代主要是借助 “栈” 这个数据结构来实现的。

AC代码

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) {
        // write code here
        if (root == null) {
            return null;
        }
        List<Integer> preList = new ArrayList<>();
        List<Integer> midList = new ArrayList<>();
        List<Integer> postList = new ArrayList<>();
        preIteOrders(root, preList);
        midIteOrders(root, midList);
        postIteOrders(root, postList);
        int size = preList.size();
        int[][] result = new int[3][size];
        for(int i = 0; i < size; i ++) {
            result[0][i] = preList.get(i);
            result[1][i] = midList.get(i);
            result[2][i] = postList.get(i);
        }
        return result;
    }

    //前序遍历-递归
    public void preOrders(TreeNode root, List<Integer> preList) {
        if(root == null) {
            return;
        }
        // 跟节点存储到结果集
        preList.add(root.val);
        // 同样的方式处理左节点
        preOrders(root.left, preList);
        // 同样的方式处理右节点
        preOrders(root.right, preList);
    }
    // 中序遍历-递归
    public void midOrders(TreeNode root, List<Integer> midList) {
        if (root == null) {
            return;
        }
        // 先遍历到左节点
        midOrders(root.left, midList);
        // 遍历到最后一个左节点，加入到集合中
        midList.add(root.val);
        // 遍历右节点
        midOrders(root.right, midList);
    }
    // 后序遍历-递归
    public void postOrders(TreeNode root, List<Integer> postList) {
        if (root == null) {
            return;
        }
        // 先遍历左节点
        postOrders(root.left, postList);
        // 在遍历右节点
        postOrders(root.right, postList);
        // 加入到集合中
        postList.add(root.val);
    }
    // 先序遍历-迭代
    public void preIteOrders(TreeNode root, List<Integer> preList) {
        if (root == null) {
            return;
        }
        // 用栈来存储
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            preList.add(node.val);
             // 在入队右节点
            if (node.right != null) {
                stack.push(node.right);
            }
            // 先入队左节点
            if (node.left != null) {
                stack.push(node.left);
            }

        }
    }
    // 中序遍历-迭代
    public void midIteOrders(TreeNode root, List<Integer> midList) {
        if (root == null) {
            return;
        }
        TreeNode cur = root;
        // 队列
        Stack<TreeNode> stack = new Stack<>();
        while (cur != null || !stack.isEmpty()) {
            // 一直迭代到最左的节点
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            // 入队
            cur = stack.pop();
            midList.add(cur.val);
            // 开始迭代右节点
            cur = cur.right;
        }
    }
    // 后序遍历-迭代
    public void postIteOrders(TreeNode root, List<Integer> postList) {
        if (root == null) {
            return;
        }
        // 用两个栈来实现
        // 通过 stack1 和 stack2 来配合可以实现 左 - 右 - 中的顺序
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        stack1.push(root);
        while (!stack1.isEmpty()) {
            TreeNode node = stack1.pop();
            stack2.push(node);
            // 先入左节点
            if (node.left != null) {
                stack1.push(node.left);
            }
            // 在入右节点
            if (node.right != null) {
                stack1.push(node.right);
            }

        }
        // 弹出元素
         while (!stack2.isEmpty()) {
                postList.add(stack2.pop().val);
         }
    }

}