树的前序遍历、中序遍历、后序遍历，java实现

Z时代
2024-01-10
分类：综合

java

1、三种遍历属于深度优先搜索（DFS），所谓前中后其实是指遍历时每个节点被访问的相对顺序。

前序遍历。节点→左孩子→右孩子 preorder

中序遍历。左孩子→节点→右孩子 inorder

后序遍历。左孩子→右孩子→节点 postorder

2、宽度优先搜索（BFS）就是从上到下，从左到右一层一层一个一个的访问

上图from leetcode

这样记忆就会很方便。

下面是代码：

一、前序遍历，LinkedList既可以当成栈来使用，又可以当成队列来使用

从根节点开始，每次迭代弹出当前栈顶元素，并将其孩子节点压入栈中，先压右孩子再压左孩子。输出【1，2，3，4，5】

package helloworld;
import java.util.LinkedList;
class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x){
        val=x;
    }
}
public class Helloworld{
    public LinkedList<Integer> preOrder(TreeNode root){
        LinkedList<TreeNode> stack = new LinkedList<>();
        LinkedList<Integer> output = new LinkedList<>();
        if (root == null) {
          return output;
        }
        stack.add(root);
        while (!stack.isEmpty()) {
          TreeNode node = stack.pollLast();
          output.add(node.val);
          if (node.right != null) {
            stack.add(node.right);
          }
          if (node.left != null) {
            stack.add(node.left);
          }
        }
        return output;
      }
    public static void main(String[] args) {
        Helloworld h=new Helloworld();
        TreeNode root = new TreeNode(1);
        root.left=new TreeNode(2);
        root.right=new TreeNode(5);
        root.left.left=new TreeNode(3);
        root.left.right=new TreeNode(4);
        System.out.println(h.preOrder(root));
    }
}

二、中序遍历，输出[3, 2, 4, 1, 5]

方法1：递归

package helloworld;
import java.util.ArrayList;
import java.util.List;
class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x){
        val=x;
    }
}
public class Helloworld{
    public List <Integer> inOrder(TreeNode root){
        List < Integer > res = new ArrayList < > ();
        helper(root, res);
        return res;
    }
    public void helper(TreeNode root, List < Integer > res) {
        if (root != null) {
            if (root.left != null) {
                helper(root.left, res);
            }
            res.add(root.val);
            if (root.right != null) {
                helper(root.right, res);
            }
        }
      }
    public static void main(String[] args) {
        Helloworld h=new Helloworld();
        TreeNode root = new TreeNode(1);
        root.left=new TreeNode(2);
        root.right=new TreeNode(5);
        root.left.left=new TreeNode(3);
        root.left.right=new TreeNode(4);
        System.out.println(h.inOrder(root));
    }
}

方法2，基于栈遍历

package helloworld;
import java.util.*;
class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x){
        val=x;
    }
}
public class Helloworld{
    public List <Integer> inOrder(TreeNode root){
         List < Integer > res = new ArrayList < > ();
            Stack < TreeNode > stack = new Stack < > ();
            TreeNode curr = root;
            while (curr != null || !stack.isEmpty()) {
                while (curr != null) {
                    stack.push(curr);
                    curr = curr.left;
                }
                curr = stack.pop();
                res.add(curr.val);
                curr = curr.right;
            }
            return res;
    }
    public static void main(String[] args) {
        Helloworld h=new Helloworld();
        TreeNode root = new TreeNode(1);
        root.left=new TreeNode(2);
        root.right=new TreeNode(5);
        root.left.left=new TreeNode(3);
        root.left.right=new TreeNode(4);
        System.out.println(h.inOrder(root));
    }
}

三、后序遍历，输出[3, 4, 2, 5, 1]

package helloworld;
import java.util.*;
class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x){
        val=x;
    }
}
public class Helloworld{
    public List <Integer> inOrder(TreeNode root){
        LinkedList<TreeNode> stack = new LinkedList<>();
        LinkedList<Integer> output = new LinkedList<>();
        if (root == null) {
          return output;
        }
        stack.add(root);
        while (!stack.isEmpty()) {
          TreeNode node = stack.pollLast();
          output.addFirst(node.val);
          if (node.left != null) {
            stack.add(node.left);
          }
          if (node.right != null) {
            stack.add(node.right);
          }
        }
        return output;
    }
    public static void main(String[] args) {
        Helloworld h=new Helloworld();
        TreeNode root = new TreeNode(1);
        root.left=new TreeNode(2);
        root.right=new TreeNode(5);
        root.left.left=new TreeNode(3);
        root.left.right=new TreeNode(4);
        System.out.println(h.inOrder(root));
    }
}