递归实现二叉树的遍历——Java版

先说说二叉树的几种常见遍历方式： 一棵二叉树由三个部分组成，即：根节点，左子树，右子树 我们分别用D,L,R来表示： D -> 根节点 L -> 左子树 R -> 右子树

二叉树的遍历方式有6种：①DLR、②DRL、③LDR、④LRD、⑤RDL、⑥RLD 而最常看到的往往是以下三种： 先序遍历：DLR 中序遍历：LDR 后序遍历：LRD

思路：运用递归的方式，从节点本身出发进行遍历，在每个层级的我们都会计算一些值，将其传给相应的下一个节点。 简单的说就是带参数的方法自己调用自己的过程 （借助leetbook上的文段解释一下） 具体可以参考以下链接： 链接：https://leetcode-cn.com/leetbook/read/data-structure-binary-tree/xefb4e/ 源码在下面，供大家参考

先序遍历：

输出顺序：D->L->R 下面展示一些 内联代码片。

// An highlighted block
import java.util.List;
import java.util.ArrayList;

public class Solution {
          
   
	public static void main(String[]args) {
          
   
		TreeNode node1=new TreeNode(1);
		node1.right = new TreeNode(3);
		Solution sol = new Solution();
		System.out.println(sol.preorderTraversal(node1));
	}
	public List<Integer> preorderTraversal(TreeNode root){
          
   
		List<Integer> list = new ArrayList<Integer>();
		preOrder(list,root);
		return list;
	}
	public void preOrder(List<Integer> list,TreeNode root) {
          
   
		if(root == null) {
          
   
			return;
		}
		list.add(root.val);
		preOrder(list,root.left);
		preOrder(list,root.right);
	}
}

中序遍历：

输出顺序：L->D->R

// An highlighted block
import java.util.ArrayList;
import java.util.List;
public class Solution {
          
   
	public static void main(String[]args) {
          
   
		Solution sol = new Solution();
		TreeNode node1 = new TreeNode(1);
		node1.left = new TreeNode(2);
		node1.right = new TreeNode(3);
		node1.right.left = new TreeNode(4);
		System.out.println(sol.inorderTraversal(node1));
	}
	public List<Integer> inorderTraversal(TreeNode root) {
          
   
		List<Integer> list = new ArrayList<>();
		inOrder(list,root);
		return list;
	}
	public void inOrder(List<Integer> list,TreeNode root) {
          
   
		if(root == null) {
          
   
			return;
		}
		inOrder(list,root.left);
		list.add(root.val);
		inOrder(list,root.right);
	}
}

后序遍历：

输出顺序：L->R->D

// An highlighted block
import java.util.ArrayList;
import java.util.List;

public class Solution {
          
   
	public static void main(String[]args) {
          
   
		Solution sol = new Solution();
		TreeNode node = new TreeNode(1);
		node.left=new TreeNode(2);
		node.right=new TreeNode(3);
		System.out.println(sol.postorderTraversal(node));
	}
	public List<Integer> postorderTraversal(TreeNode root){
          
   
		List<Integer> list = new ArrayList<>();
		postOrder(list,root);
		return list;
	}
	public void postOrder(List<Integer> list,TreeNode root) {
          
   
		if(root == null) {
          
   
			return;
		}
		postOrder(list,root.left);
		postOrder(list,root.right);
		list.add(root.val);
	}
}