首页 > 其他分享 >Day11(二叉树) | 二叉树的递归遍历 二叉树的迭代遍历 二叉树的统一迭代法 二叉树层序遍历

Day11(二叉树) | 二叉树的递归遍历 二叉树的迭代遍历 二叉树的统一迭代法 二叉树层序遍历

时间:2024-07-15 21:29:22浏览次数:17  
标签:node 遍历 st 二叉树 迭代法 null root 节点 result

二叉树的递归遍历

终于来到了递归!!!递归是进入动态规划的第一步,有部分的递归完全可以写成动态规划!这里可以移步到左程云的视频观看.

递归的步骤:

  1. 确定递归函数的参数和返回值: 确定哪些参数是递归的过程中需要处理的,那么就在递归函数里加上这个参数, 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。

  2. 确定终止条件: 写完了递归算法, 运行的时候,经常会遇到栈溢出的错误,就是没写终止条件或者终止条件写的不对,操作系统也是用一个栈的结构来保存每一层递归的信息,如果递归没有终止,操作系统的内存栈必然就会溢出。

  3. 确定单层递归的逻辑: 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。

代码如下 :

// 前序遍历·递归·LC144_二叉树的前序遍历
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        preorder(root, result);
        return result;
    }

    public void preorder(TreeNode root, List<Integer> result) {
        if (root == null) {
            return;
        }
        result.add(root.val);
        preorder(root.left, result);
        preorder(root.right, result);
    }
}
// 中序遍历·递归·LC94_二叉树的中序遍历
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        inorder(root, res);
        return res;
    }

    void inorder(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }
        inorder(root.left, list);
        list.add(root.val);             // 注意这一句
        inorder(root.right, list);
    }
}
// 后序遍历·递归·LC145_二叉树的后序遍历
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        postorder(root, res);
        return res;
    }

    void postorder(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }
        postorder(root.left, list);
        postorder(root.right, list);
        list.add(root.val);             // 注意这一句
    }
}

二叉树的迭代遍历

迭代法很麻烦,我觉得用递归挺好的

// 前序遍历顺序:中-左-右,入栈顺序:中-右-左
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;
    }
}

二叉树的统一迭代法

迭代法确实很复杂

迭代法前序遍历代码如下:

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        Stack<TreeNode> st = new Stack<>();
        if (root != null) st.push(root);
        while (!st.empty()) {
            TreeNode node = st.peek();
            if (node != null) {
                st.pop(); // 将该节点弹出,避免重复操作,下面再将右中左节点添加到栈中
                if (node.right!=null) st.push(node.right);  // 添加右节点(空节点不入栈)
                if (node.left!=null) st.push(node.left);    // 添加左节点(空节点不入栈)
                st.push(node);                          // 添加中节点
                st.push(null); // 中节点访问过,但是还没有处理,加入空节点做为标记。
                
            } else { // 只有遇到空节点的时候,才将下一个节点放进结果集
                st.pop();           // 将空节点弹出
                node = st.peek();    // 重新取出栈中元素
                st.pop();
                result.add(node.val); // 加入到结果集
            }
        }
        return result;
    }
}

迭代法中序遍历代码如下:

class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
    Stack<TreeNode> st = new Stack<>();
    if (root != null) st.push(root);
    while (!st.empty()) {
        TreeNode node = st.peek();
        if (node != null) {
            st.pop(); // 将该节点弹出,避免重复操作,下面再将右中左节点添加到栈中
            if (node.right!=null) st.push(node.right);  // 添加右节点(空节点不入栈)
            st.push(node);                          // 添加中节点
            st.push(null); // 中节点访问过,但是还没有处理,加入空节点做为标记。

            if (node.left!=null) st.push(node.left);    // 添加左节点(空节点不入栈)
        } else { // 只有遇到空节点的时候,才将下一个节点放进结果集
            st.pop();           // 将空节点弹出
            node = st.peek();    // 重新取出栈中元素
            st.pop();
            result.add(node.val); // 加入到结果集
        }
    }
    return result;
}
}

迭代法后序遍历代码如下:

class Solution {
   public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        Stack<TreeNode> st = new Stack<>();
        if (root != null) st.push(root);
        while (!st.empty()) {
            TreeNode node = st.peek();
            if (node != null) {
                st.pop(); // 将该节点弹出,避免重复操作,下面再将右中左节点添加到栈中
                st.push(node);                          // 添加中节点
                st.push(null); // 中节点访问过,但是还没有处理,加入空节点做为标记。
                if (node.right!=null) st.push(node.right);  // 添加右节点(空节点不入栈)
                if (node.left!=null) st.push(node.left);    // 添加左节点(空节点不入栈)         
                               
            } else { // 只有遇到空节点的时候,才将下一个节点放进结果集
                st.pop();           // 将空节点弹出
                node = st.peek();    // 重新取出栈中元素
                st.pop();
                result.add(node.val); // 加入到结果集
            }
        }
        return result;
   }
}

二叉树层序遍历

据说层序遍历学会可以打十道题

后面把这十道题补上 :

代码如下 :

// 102.二叉树的层序遍历
class Solution {
    public List<List<Integer>> resList = new ArrayList<List<Integer>>();

    public List<List<Integer>> levelOrder(TreeNode root) {
        //checkFun01(root,0);
        checkFun02(root);

        return resList;
    }

    //BFS--递归方式
    public void checkFun01(TreeNode node, Integer deep) {
        if (node == null) return;
        deep++;

        if (resList.size() < deep) {
            //当层级增加时,list的Item也增加,利用list的索引值进行层级界定
            List<Integer> item = new ArrayList<Integer>();
            resList.add(item);
        }
        resList.get(deep - 1).add(node.val);

        checkFun01(node.left, deep);
        checkFun01(node.right, deep);
    }

    //BFS--迭代方式--借助队列
    public void checkFun02(TreeNode node) {
        if (node == null) return;
        Queue<TreeNode> que = new LinkedList<TreeNode>();
        que.offer(node);

        while (!que.isEmpty()) {
            List<Integer> itemList = new ArrayList<Integer>();
            int len = que.size();

            while (len > 0) {
                TreeNode tmpNode = que.poll();
                itemList.add(tmpNode.val);

                if (tmpNode.left != null) que.offer(tmpNode.left);
                if (tmpNode.right != null) que.offer(tmpNode.right);
                len--;
            }

            resList.add(itemList);
        }

    }
}

标签:node,遍历,st,二叉树,迭代法,null,root,节点,result
From: https://www.cnblogs.com/flydandelion/p/18304013

相关文章

  • 矩阵优化 DP 以及全局平衡二叉树实现的动态 DP 学习笔记
    矩阵乘法求斐波那契数列的第\(n\)项,其中\(n\le10^{18}\),对数\(m\)取模。写出转移方程,\(f_i=f_{i-1}+f_{i-2}\),直接算是\(O(n)\)的,似乎没什么办法优化。定义大小分别为\(n\timesp\)和\(p\timesm\)的矩阵(分别为\(a\)和\(b\))相乘的结果(矩阵\(c\))是一个大小为\(......
  • 数据结构-二叉树
    引入图论中的树和现实生活中的树长得一样,只不过我们习惯于处理问题的时候把树根放到上方来考虑。这种数据结构看起来像是一个倒挂的树,因此得名。定义一个没有固定根结点的树称为无根树(unrootedtree)。无根树有几种等价的形式化定义:有n个结点,n-1条边的连通无向图无向无环......
  • 树的遍历
    幻影忍者前情提要这是一棵二叉树,现在,我们要对它进行遍历<( ̄︶ ̄)>前序遍历顺序先根节点,再左节点,再右节点实现如果树为空,返回,否则:访问根节点若根节点有左孩子,前序遍历左子树若根节点有右孩子,前序遍历右子树所以,让我们来实现一下该树的前序遍历:根节点\(1\)->左孩......
  • 「代码随想录算法训练营」第十一天 | 二叉树 part1
    二叉树的基本知识链接:https://programmercarl.com/二叉树理论基础.html要点:深度优先遍历前序遍历(递归法,迭代法)中序遍历(递归法,迭代法)后序遍历(递归法,迭代法)广度优先遍历层次遍历(迭代法)由于栈就是递归的一种实现结构,因此前中后序遍历的逻辑可以借助栈使用递归的方式......
  • java List集合转Map并遍历输出
    1.使用流转map并且遍历packagecom.demo.toMap;importjava.util.ArrayList;importjava.util.List;importjava.util.Map;importjava.util.stream.Collectors;publicclassMianDemo{publicstaticvoidmain(String[]args){List<NodeList>list=......
  • 代码随想录算法训练营第22天 |二叉树part07:235. 二叉搜索树的最近公共祖先、701.二叉
    代码随想录算法训练营第22天|二叉树part07:235.二叉搜索树的最近公共祖先、701.二叉搜索树中的插入操作、450.删除二叉搜索树中的节点235.二叉搜索树的最近公共祖先https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/description/代码随想录:htt......
  • LeetCode 144. 二叉树的前序遍历
    更多题解尽在https://sugar.matrixlab.dev/algorithm每日更新。组队打卡,更多解法等你一起来参与哦!LeetCode144.二叉树的前序遍历,难度中等。classSolution{publicvoidpreorderTraversal(TreeNoderoot,List<Integer>ans){if(root==null)re......
  • Python数据容器(3)--遍历与列表生成式
    文章目录遍历直接遍历索引遍历list列表tuple元组字典遍历get()方法items()方法enumerate()函数与zip()函数enumerate()函数zip()函数列表生成式语法表现形式编写基本的列表生成式带有条件的列表生成式嵌套列表生成式字符串与列表之间的转换总结遍历:列表生成式遍......
  • 树的层次遍历
    树的层次遍历是指按层次顺序访问树中所有节点的遍历方式。具体的步骤如下:从根节点开始,将根节点入队。进行循环,直到队列为空:弹出队列中的节点,并访问该节点。将该节点的所有子节点依次入队。完成遍历。层次遍历的相关知识点:队列:层次遍历需要使用一个队列来暂存节点。每次......
  • 【数据结构与算法】详解二叉树下:实践篇————通过链式结构深入理解并实现二叉树
          ......