二叉树遍历分为前序遍历、中序遍历、后序遍历、分层遍历
它的实现可以使用递归或迭代方法。
递归遍历
这里帮助你识别递归算法的三个要素。每次写递归，都按照这三个要素来写，这样可以保证大家都能写出正确的递归算法！
确定递归函数的参数和返回值：确定递归过程中需要处理哪些参数，然后把这个参数加到递归函数中，还要明确每个递归的返回值是什么，确定递归的返回类型递归函数。确定终止条件：递归算法写好后，在运行的时候，经常会遇到栈溢出错误，即没有写完终止条件或者写错了终止条件。操作系统也使用栈结构来存储每一层递归的信息。，如果递归不终止二叉树遍历算法 java，操作系统的内存栈必然会溢出。确定单级递归的逻辑：确定每个递归级别需要处理的信息。在这里，它会反复调用自己来实现递归过程。
下面是一个前序遍历的例子：
确定递归函数的参数和返回值：因为需要打印出前序遍历节点的值，所以需要在参数中传入List存储节点的值。除此之外，不需要处理任何数据或返回值，所以递归函数的返回类型为void，代码如下：
private void preOrder(List list, TreeNode root)
确定终止条件：在递归的过程中，怎样才能认为递归已经结束？当然，当前遍历的节点是空的，那么这一层的递归就要结束了，所以如果当前遍历的节点是空的，直接就可以了，代码如下：
if(root==null) return;
确定单级递归的逻辑：前序遍历是中左的顺序，所以单级递归的逻辑是先取中间节点的值。代码如下：
if(root!=null) list.add(root.val);//中
if(root.left!=null) preOrder(list,root.left);//左
if(root.right!=null) preOrder(list,root.right);//右
单级递归的逻辑按照中左顺序进行处理，这样二叉树的前序遍历就基本完成了。我们来看看完整的代码：
package 力扣;
import java.util.ArrayList;
import java.util.List;
/**
* @author yyq
* @create 2022-04-06 10:30
* 二叉树的前序遍历
* 实现方式:
* 1.递归遍历
* 2.迭代遍历
*
*/
public class leetcode144 {
public List preorderTraversal(TreeNode root) {
List list = new ArrayList();
if(root!=null)
preOrder(list,root);
return list;
}
private void preOrder(List list, TreeNode root) {
if(root==null) return;
if(root!=null) list.add(root.val);
if(root.left!=null) preOrder(list,root.left);
if(root.right!=null) preOrder(list,root.right);
}
}
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
由于二叉树的递归遍历类似，后两种实现在此不再赘述。
迭代遍历 （迭代法）
前序遍历在中间和左侧。每次先处理中间节点【技术】递归算法的三个要素（一）——递归递归
，然后先将根节点入栈，再将右孩子入栈，再将左孩子入栈。
为什么要先添加右孩子二叉树遍历算法 java，然后再添加左孩子？因为这是出栈时的中左顺序。
（注意代码中的空节点不会被压入栈中）
public List preorderIterative(TreeNode root) {
List list = new ArrayList();
Stack stack=new Stack();
if(root!=null) stack.push(root);
else return list;
while (!stack.isEmpty()){
TreeNode pop = stack.pop();
list.add(pop.val);
if(pop.right!=null)
stack.push(pop.right);
if(pop.left!=null)
stack.push(pop.left);
}
return list;
}
中序遍历（迭代法）
为了解释清楚，我解释一下，在刚才的迭代过程中，我们其实有两个操作：
处理：将元素放入列表集合访问：遍历节点
分析一下刚才写的前序遍历代码为什么不能和中序遍历一样使用，因为前序遍历的顺序是中左，最先访问的元素是中间节点，要遍历的元素被处理的也是中间节点，所以只能写刚才。代码比较简洁，因为要访问的元素和要处理的元素顺序一致，都是中间节点。
然后看中序遍历。中序遍历是左、中、右。首先访问二叉树顶部的节点，然后逐层访问，直到到达树的左侧底部，然后开始处理节点（即在Put中的值节点放入数组中），导致处理顺序和访问顺序不一致。
那么，在使用迭代的方式编写中序遍历时，需要使用指针遍历来帮助访问节点，而栈则用于处理节点上的元素。
动画如下：
public List inorderIterative(TreeNode root) {
List list=new ArrayList();
Stack stack=new Stack();
if(root == null) return list;
TreeNode temp=root;
stack.push(root);
while (!stack.isEmpty()){
if(temp.left!=null){
stack.push(temp.left);
temp=temp.left;
}else {
TreeNode pop = stack.pop();
list.add(pop.val);
if(pop.right!=null){
temp= pop.right;
stack.push(pop.right);
}
}
}
return list;
}
后序遍历（迭代法）
让我们看一下后序遍历。前序遍历是中间左右，后续遍历是左右中间。那么我们只需要调整前序遍历的代码顺序，变成中右左遍历顺序，然后将数组倒过来，输出结果。顺序为左右，如下图：
因此后序遍历只需要对前序遍历的代码稍作修改即可。代码如下：
// 后序遍历顺序 左-右-中 入栈顺序：中-左-右 出栈顺序：中-右-左， 最后翻转结果
class Solution {
public List postorderTraversal(TreeNode root) {
List result = new ArrayList();
if (root == null){
return result;
}
Stack stack = new Stack();
stack.push(root);
while (!stack.isEmpty()){
TreeNode node = stack.pop();
result.add(node.val);
if (node.left != null){
stack.push(node.left);
}
if (node.right != null){
stack.push(node.right);
}
}
Collections.reverse(result);
return result;
}
}
文章来源:https://blog.csdn.net/weixin_40422192/article/details/123990643