当前位置: 首页 > news >正文

二叉树遍历/算法数据结构

六、树

6.1遍历算法
6.1.1前中后序
  • 在做递归时,最重要是三步骤

    1. 确定递归函数的返回值和参数

    2. 确定终止条件

    3. 确定单层递归的逻辑

      伪代码
      void travel(cur, vec) {if (cur == null) {return ;}vec.push(cur->middle, vec);  // 递归中节点vec.push(cur->left, vec);    // 递归左节点vec.push(cur->right, vec);   // 递归右节点
      }
      
    • 其实很简单,参数就是要目前遍历节点在哪,返回值也同理,终止条件就是指遍历到null的时候回溯,逻辑不要想复杂,根据顺序移动上述上个递归函数即可

    • 前顺遍历

      class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();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);  // 右子树}
      }
      
    • 中序遍历

      class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();inorder(root, res);return res;}public void inorder(TreeNode root, List<Integer> res) {if (root == null) {return;}inorder(root.left, res);res.add(root.val);inorder(root.right, res);}
      }
      
    • 后序遍历

      class Solution {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();postorder(root, result);return result;}public void postorder(TreeNode root, List<Integer> result) {if (root == null) {return;}postorder(root.left, result);   postorder(root.right, result);result.add(root.val);}
      }
      
    • 其实很简单,根据遍历的顺序摆放遍历顺序和添加元素的顺序,(root.left, result)代表左子树,(root.right, result)代表右子树,(root.val)代表中节点。

    • 递归

    • 前序(要理解遍历的核心,先把中节点塞入,然后根据栈去模拟,先加入右节点然后是左节点,移动到左节点继续加入)

      class Solution {public List<Integer> preorderTraversal(TreeNode root) {Stack<TreeNode> stack = new Stack<>();List<Integer> res = new ArrayList<>();if (root == null){return res;}stack.push(root);while (!stack.isEmpty()) {TreeNode temp = stack.pop();res.add(temp.val);if (temp.right != null) {stack.push(temp.right);}if (temp.left != null) {stack.push(temp.left);}}return res;}
      }
      
    • 中序(核心就是每收集一个元素到res数组中,其实都是以中节点的姿态进入,这也对应了为什么if循环为什么要push一个null节点,前中后也只要交换顺序即可)

      class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();Stack<TreeNode> stack = new Stack<>();if (root != null) stack.push(root);while (!stack.isEmpty()) {TreeNode temp = stack.peek();if (temp != null) {stack.pop();if (temp.right != null) stack.add(temp.right);stack.push(temp);stack.push(null);if (temp.left != null) stack.add(temp.left);}else {stack.pop();temp = stack.peek();stack.pop();res.add(temp.val);}}return res;}
      }
      
    • 后序(就是前序遍历的左右调换顺序,然后再倒叙结果数组)

      class Solution {public List<Integer> postorderTraversal(TreeNode root) {Stack<TreeNode> stack = new Stack<>();List<Integer> res = new ArrayList<>();if (root == null){return res;}stack.push(root);while (!stack.isEmpty()) {TreeNode temp = stack.pop();res.add(temp.val);if (temp.left != null) {stack.push(temp.left);}if (temp.right != null) {stack.push(temp.right);}}Collections.reverse(res);return res;}
      }
      
6.1.2层序遍历
  1. 递归算法,一般递归就是深度优先了,要明确三要素,一般遍历就是参数为当前处理节点+加其它附属条件,循环处理按照顺序(这里是左到右),结束条件都是到底直接返回

    class Solution {List<List<Integer>> res = new ArrayList<List<Integer>>();public List<List<Integer>> levelOrder(TreeNode root) {check(root, 0);return res;}public void check(TreeNode temp, int deep) {if (temp == null) {return;}deep++;if (res.size() < deep) {  // 创建数组的条件,不可能预先创建的List<Integer> res1 = new ArrayList<>();res.add(res1);}res.get(deep-1).add(temp.val);  // 注意为deep-1,区分索引和深度的区别check(temp.left, deep);  // 左子树check(temp.right, deep);  // 右子树}
    }
    
  2. 迭代,就是按照队列,先进先出,按照层数模拟也就是广度优先遍历

    class Solution {public List<List<Integer>> levelOrder(TreeNode root) {Deque<TreeNode> queue = new ArrayDeque<>();List<List<Integer>> res = new ArrayList<List<Integer>>();  // 结果二维数组if (root != null) {queue.addLast(root);  // 防止root为空}while (!queue.isEmpty()) {int size = queue.size();  // size代表每一层几个元素List<Integer> res1 = new ArrayList<>();while (size > 0) {  // size为0这一层就停止TreeNode temp =  queue.removeFirst();res1.add(temp.val);if (temp.left != null) queue.addLast(temp.left);  // 左节点if (temp.right != null) queue.addLast(temp.right);  // 右节点size--;  // 记得减一}res.add(res1);}return res;}
    }
    

http://www.mrgr.cn/news/69935.html

相关文章:

  • Redisson的可重入锁
  • RabbitMQ 在 Linux CentOS 和 Docker 环境下的部署及分布式部署指南
  • 【机器学习】机器学习中用到的高等数学知识
  • Vue3 -- 环境变量的配置【项目集成3】
  • Python自动化运维DevSecOps与安全自动化
  • 网络物理隔离技术
  • 【系统架构设计师】2024年下半年真题论文: 论软件维护及其应用(包括参考素材)
  • 使用 MMDetection 实现 Pascal VOC 数据集的目标检测项目练习(五) pycharm
  • 渺小与伟大:人类的宇宙奇特之旅
  • C语言:文件操作2(又一万字?)
  • C++ : STL容器(适配器)之stack、queue剖析
  • LocalDate和LocalDateTime类
  • 「Mac玩转仓颉内测版3」入门篇3 - Cangjie的基本语法与结构
  • Jquery向指定HTML标签追加新元素教程
  • 005.精读《B-Tree vs LSM-Tree》
  • 浙江大学高等数学研究所已变样
  • 网站架构知识之Ansible模块(day021)
  • SpringBoot中的两种字段自动填充方式
  • HTTP —— OSI七层模型
  • 在 Mac 上使用 Docker 安装宝塔并部署 LNMP 环境
  • SCAU 华南农业大学 高级程序设计语言(C语言) 教材习题题解
  • distances = np.linalg.norm(data[:, None] - centers, axis=2)
  • spring-security(记住密码,CSRF)
  • C#-抽象类、抽象函数
  • 腾讯云双11狂欢:拼团优惠、会员冲榜、限时秒杀,多重好礼等你来拿!
  • 论文解读之SDXL: Improving Latent Diffusion Models forHigh-Resolution Image Synthesis