二叉树递归遍历

2024-03-21 本文已影响0人宗驴

需求：

给你二叉树的根节点 root ，返回它节点值的前序、中序、后续遍历。
示例后文件尾部，验证结果。

思路：

遍历二叉数主要使用递归的形式完成。俗话说一入递归深似海，这话说的不错，以前不太关注递归，也没感觉到。使用到的时候才感受到递归的深度。递归经常出现条件不好定义结束条件不好确认等问题，那么我们来看下递归的几个步骤（这个是实现递归的基础）：
一、确定递归函数的参数和返回值
确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数，并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
二、确定终止条件：
写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。
三、确定单层递归的逻辑：
确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。

有以上三点递归函数就很容易实现了。

以下以前序遍历为例：

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

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

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

 if(root == null){return;}

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

        result.add(root.val);
        preorder(result,root.left);
        preorder(result,root.right);

这里还有个重点需要了解下
为什么都是在中节点的时候赋值？
根据二叉数的结果最终左节点还是有节点都会成为末尾节点，末尾节点是没有左右节点的，其实这也是一个中节点，只是这个中节点的左右子节点都是null。所以中节点就是赋值的节点。

leetcode题目链接：前序遍历
 leetcode题目链接：中序遍历
 leetcode题目链接：后序遍历

/**
 * 二叉树遍历
 * 可以简单的理解前中后需为中函数的位置
 */
public class Traversal {
    List<Integer> result = new ArrayList<>();
    /**
     * 前序遍历 144
     * 左右中
     * @param root
     * @return
     */
    public List<Integer> preorderTraversal(TreeNode root) {

        List<Integer> result = new ArrayList<>();
        preorder(result,root);
        return result;
    }

    /**
     * 前序遍历递归 144
     * @param result
     * @param root
     */
    public  void preorder(List<Integer> result , TreeNode root){
        if(root == null){return;}

        // 递归到最后一层null前左右都会变成中节点
        // 最后一层，没有左右节点缓存值。
        // 根据前序概念，中在最前，所以在最前复制
        result.add(root.val);
        preorder(result,root.left);
        preorder(result,root.right);
    }


    /**
     * 中序遍历 94
     * @param root
     * @return
     */
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        inorder(root, res);
        return res;
    }

    /**
     * 中序遍历 94
     * @param root
     * @param list
     */
    void inorder(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }
        inorder(root.left, list);
        list.add(root.val);
        inorder(root.right, list);
    }


    /**
     * 后续遍历 145
     * @param root
     * @return
     */
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        postorder(root, res);
        return res;
    }

    /**
     * 后续遍历145
     * @param root
     * @param list
     */
    void postorder(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }
        postorder(root.left, list);
        postorder(root.right, list);
        list.add(root.val);
    }
}


/**
 *  Definition for a binary tree node.
 */
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;
     }
 }

示例 1：