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

递归实现二叉树的遍历——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 blockimport 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 preorderTraversal(TreeNode root){List list = new ArrayList();preOrder(list,root);return list;}public void preOrder(List list,TreeNode root) {if(root == null) {return;}list.add(root.val);preOrder(list,root.left);preOrder(list,root.right);}}

中序遍历：

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

// An highlighted blockimport 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 inorderTraversal(TreeNode root) {List list = new ArrayList<>();inOrder(list,root);return list;}public void inOrder(List list,TreeNode root) {if(root == null) {return;}inOrder(list,root.left);list.add(root.val);inOrder(list,root.right);}}

后序遍历：

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

// An highlighted blockimport 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 postorderTraversal(TreeNode root){List list = new ArrayList<>();postOrder(list,root);return list;}public void postOrder(List list,TreeNode root) {if(root == null) {return;}postOrder(list,root.left);postOrder(list,root.right);list.add(root.val);}}