二叉树的深度优先遍历（力扣94,144,145）

文章目录

• 题目
• 前知
• • 二叉树的遍历方式有什么？
  • 递归和迭代是什么？
• 题解
• • 一、思路
  • 二、解题方法
  • 三、Code
• 总结

题目

Problem: 144. 二叉树的前序遍历
Problem: 94. 二叉树的中序遍历
Problem: 145. 二叉树的后序遍历

前知

二叉树的遍历方式有什么？

二叉树主要有两种遍历方式：

1.深度优先遍历(BFS)：先往深走，遇到叶子节点再往回走。

• 前序遍历（递归法，迭代法）
• 中序遍历（递归法，迭代法）
• 后序遍历（递归法，迭代法）

2.广度优先遍历(DFS)：一层一层的去遍历
层次遍历（迭代法）

递归和迭代是什么？

递归是一种函数调用自身的过程。迭代是通过重复执行一系列指令来解决问题的过程。在处理大规模问题时通常更高效。但是，对于某些问题，递归可能更直观和简洁。选择递归还是迭代取决于具体的问题和实现需求。一般来说，递归可以用于解决分而治之的问题，例如树的遍历和图的搜索等。而迭代通常用于处理循环、列表和数组等重复性任务。

题解

一、思路

1.递归

PS:以中序遍历举例，其它两个都只需要调换第三步代码位置，其它都相同

递归三要素
1.确定递归函数的参数和返回值：因为要打印出中序遍历节点的数值，所以参数里需要传入List来放节点的数值，除了这一点就不需要再处理什么数据了也不需要有返回值，所以递归函数返回类型就是void

public void inorder(TreeNode root,List<Integer> result) 

2.确定终止条件：在递归的过程中，如何算是递归结束了呢，当然是当前遍历的节点是空了，那么本层递归就要结束了，所以如果当前遍历的这个节点是空，就直接return

if(root == null) {
            return;
        }

3.确定单层递归的逻辑：中序遍历是左中右的循序，所以在单层递归的逻辑，是要先取中节点的数值

        inorder(root.left,result); //左
        result.add(root.val);	   //中
        inorder(root.right,result);//右

2.迭代

PS:中序和前序后序两种在迭代上面略有差异

• 前序遍历

先将根节点放入栈中，出栈添加到数组里，再将右孩子加入栈中，最后加入左孩子，这样出栈的时候才是中左右的顺序

• 中序遍历

先访问的是二叉树顶部的节点，然后一层一层向下访问，直到到达树左面的最底部，再开始处理节点，弹出栈顶元素，并将其添加到result数组中，再向上出栈一个，再出栈右孩子,重复这个过程

• 后序遍历

先将根节点放入栈中，出栈添加到数组里，再将左孩子加入栈中，最后加入右孩子，这样出栈的时候才是中右左的顺序，再对数组进行翻转操作得到左右中（实际上是将前序遍历的左右孩子插入顺序换个位置，再对数组进行翻转）

二、解题方法

1.递归：inorder递归函数返回值void，传入参数为root根节点和result集合，终止条件为当根节点为空时，退出递归防止栈溢出，按照左中右的顺序进行递归，在主函数里创建result集合，调用递归函数

2.迭代：中序遍历是访问到左边最低端才开始出栈。而前序和后序都是刚开始就出栈根节点，然后左右孩子看顺序入栈出栈

三、Code

• 递归

/**
 * Definition for a binary tree node.
 * public 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;
 *     }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        inorder(root,result);
        return result;
    }
    public void inorder(TreeNode root,List<Integer> result) {
        if(root == null) {
            return;
        }
        inorder(root.left,result); //左
        result.add(root.val);	   //中
        inorder(root.right,result);//右
    }
}

• 迭代

// 前序遍历顺序：中-左-右，入栈顺序：中-右-左
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null){
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            result.add(node.val);
            if (node.right != null){
                stack.push(node.right);
            }
            if (node.left != null){
                stack.push(node.left);
            }
        }
        return result;
    }
}

// 中序遍历顺序: 左-中-右 入栈顺序： 左-右
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null){
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()){
           if (cur != null){
               stack.push(cur);
               cur = cur.left;
           }else{
               cur = stack.pop();
               result.add(cur.val);
               cur = cur.right;
           }
        }
        return result;
    }
}

// 后序遍历顺序 左-右-中 入栈顺序：中-左-右 出栈顺序：中-右-左， 最后翻转结果
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null){
            return result;
        }
        Stack<TreeNode> 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;
    }
}

总结

以上就是针对这道题的刷题笔记，讲解了二叉树DFS的两种方式，递归和迭代，递归三种都是类似的，而迭代中序和其它两个不太相同