文章目录
  1. 1. 前序
    1. 1.1. 递归
    2. 1.2. 非递归
  2. 2. 中序
    1. 2.1. 递归
    2. 2.2. 非递归
  3. 3. 后序
    1. 3.1. 递归
    2. 3.2. 非递归

【题目】:二叉树的前序、中序、后序的递归和非递归实现。

非递归实现实际上是模拟递归实现,所以可以使用Stack这种数据结构。

前序

递归

void preOrder(TreeNode root) {
    if (root != null) {
        System.out.println(root.val);
        preOrder(root.left);
        preOrder(root.right);
    }
} 

非递归

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList<Integer>();
    Stack<TreeNode> stack = new Stack<TreeNode>();

    while (root != null || !stack.isEmpty()) {
        while (root != null) {
            list.add(root.val);
            stack.push(root);
            root = root.left;
        }

        if (!stack.isEmpty()) {
            root = stack.pop();
            root = root.right;
        }

    }

    return list;
}

中序

递归

void inOrder(TreeNode root) {
    if (root != null) {
        inOrder(root.left);
        System.out.println(root.val);
        inOrder(root.right);
    }
} 

非递归

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList<Integer>();
    Stack<TreeNode> stack = new Stack<TreeNode>();

    while (root != null || !stack.isEmpty()) {
        while (root != null) {
            stack.push(root);
            root = root.left;
        }

        if (!stack.isEmpty()) {
            root = stack.pop();
            list.add(root.val);
            root = root.right;
        }

    }

    return list;
}

后序

递归

void postOrder(TreeNode root) {
    if (root != null) {
        postOrder(root.left);
        postOrder(root.right);
        System.out.println(root.val);
    }
} 

非递归

对于任一结点P,将其入栈,然后沿其左子树一直往下搜索,直到搜索到没有左孩子的结点,此时该结点出现在栈顶,但是此时不能将其出栈并访问,因此其右孩子还为被访问。所以接下来按照相同的规则对其右子树进行相同的处理,当访问完其右孩子时,该结点又出现在栈顶,此时可以将其出栈并访问。这样就保证了正确的访问顺序。可以看出,在这个过程中,每个结点都两次出现在栈顶,只有在第二次出现在栈顶时,才能访问它。因此需要多设置一个变量标识该结点是否是第一次出现在栈顶。

public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList<Integer>();
    Stack<BTNoode> stack = new Stack<BTNoode>();

    while (root != null || !stack.isEmpty()) {
        while (root != null) {
            BTNoode node = new BTNoode(root, true);
            stack.push(node);
            root = root.left;
        }

        if (!stack.isEmpty()) {
            BTNoode node = stack.pop();
            if (node.isFirst) {
                node.isFirst = false;
                stack.push(node);
                root = node.node.right;
            } else {
                list.add(node.node.val);
            }
        }
    }

    return list;
}

class BTNoode {
    TreeNode node;
    boolean isFirst;

    BTNoode(TreeNode node, boolean isFirst) {
        this.node = node;
        this.isFirst = isFirst;
    }
}

第二种思路:要保证根结点在左孩子和右孩子访问之后才能访问,因此对于任一结点P,先将其入栈。如果P不存在左孩子和右孩子,则可以直接访问它;或者P存在左孩子或者右孩子,但是其左孩子和右孩子都已被访问过了,则同样可以直接访问该结点。若非上述两种情况,则将P的右孩子和左孩子依次入栈,这样就保证了每次取栈顶元素的时候,左孩子在右孩子前面被访问,左孩子和右孩子都在根结点前面被访问。

public List<Integer> postorderTraversal2(TreeNode root) {
    List<Integer> list = new ArrayList<Integer>();
    Stack<TreeNode> stack = new Stack<TreeNode>();
    TreeNode preNode = null;

    if (root == null)
        return list;

    stack.push(root);
    while (!stack.isEmpty()) {

        root = stack.peek();

        if ((root.left == null && root.right == null) ||
                (preNode != null && (preNode == root.left || preNode ==root.right))) {
            list.add(root.val);
            stack.pop();
            preNode = root;
        } else {
            if (root.right != null) {
                stack.push(root.right);
            }
            if (root.left != null) {
                stack.push(root.left);
            }
        }
    }

    return list;
}
文章目录
  1. 1. 前序
    1. 1.1. 递归
    2. 1.2. 非递归
  2. 2. 中序
    1. 2.1. 递归
    2. 2.2. 非递归
  3. 3. 后序
    1. 3.1. 递归
    2. 3.2. 非递归