二叉树的前序中序后序遍历 NC 45 LC 144 LC 94 LC 145

概述

前序遍历：根节点、左子树、右子树

中序遍历：左子树、根节点、右子树

后序遍历：左子树、右子树、根节点

主要有三种遍历方法：递归、迭代、Morris遍历

递归方法：

时间复杂度：

空间复杂度：平均情况为 最坏情况为 （即树呈链状）

迭代方法：

即显式地维护递归方法中的栈

时间复杂度、空间复杂度和递归方法一致。

Morris遍历：

时间复杂度：

空间复杂度：

（代码可参考leetcode题解，等掌握了再更新...）

1. 递归遍历

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整型二维数组
     */

    List<Integer> preOrder;
    List<Integer> inOrder;
    List<Integer> postOrder;

    public int[][] threeOrders (TreeNode root) {
        // write code here
        preOrder = new ArrayList<>();
        inOrder = new ArrayList<>();
        postOrder = new ArrayList<>();
        setPreOder(root);
        setInOrder(root);
        setPostOrder(root);
        int[][] ans = new int[3][preOrder.size()];
        for (int i = 0; i < preOrder.size(); i++) {
            ans[0][i] = preOrder.get(i).intValue();
            ans[1][i] = inOrder.get(i).intValue();
            ans[2][i] = postOrder.get(i).intValue();
        }
        return ans;
    }

    private void setPreOder(TreeNode root) {
        if (root != null) {
            preOrder.add(root.val);
            setPreOder(root.left);
            setPreOder(root.right);
        }
    }

    private void setInOrder(TreeNode root) {
        if (root != null) {
            setInOrder(root.left);
            inOrder.add(root.val);
            setInOrder(root.right);
        }
    }

    private void setPostOrder(TreeNode root) {
        if (root != null) {
            setPostOrder(root.left);
            setPostOrder(root.right);
            postOrder.add(root.val);
        }
    }
}

2. 迭代遍历

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整型二维数组
     */

    List<Integer> preOrder = new ArrayList<>();
    List<Integer> inOrder = new ArrayList<>();
    List<Integer> postOrder = new ArrayList<>();

    public int[][] threeOrders (TreeNode root) {
        // write code here
        setPreOrder(root);
        setInOrder(root);
        setPostOrder(root);
        int len = preOrder.size();
        int[][] ans = new int[3][len];
        for (int i = 0; i < len; i++) {
            ans[0][i] = preOrder.get(i).intValue();
            ans[1][i] = inOrder.get(i).intValue();
            ans[2][i] = postOrder.get(i).intValue();
        }
        return ans;
    }

    private void setPreOrder(TreeNode root) {
        if (root != null) {
            Stack<TreeNode> stack = new Stack<>();
            TreeNode node = root;
            while (!stack.isEmpty() || node != null) {
                while (node != null) {
                    preOrder.add(node.val);
                    stack.push(node);
                    node = node.left;
                }
                node = stack.pop();
                node = node.right;
            }
        }
    }

    private void setInOrder(TreeNode root) {
        if (root != null) {
            Stack<TreeNode> stack = new Stack<>();
            TreeNode node = root;
            while (!stack.isEmpty() || node != null) {
                while (node != null) {
                    stack.push(node);
                    node = node.left;
                }
                node = stack.pop();
                inOrder.add(node.val);
                node = node.right;
            }
        }
    }

    private void setPostOrder(TreeNode root) {
        if (root != null) {
            Stack<TreeNode> stack = new Stack<>();
            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) {
                    postOrder.add(root.val);
                    prev = root;
                    root = null;
                } else {
                    stack.push(root);
                    root = root.right;
                }
            }
        }
    }
}