登录/ 注册
 找回密码
 立即注册
关闭

CSDN热搜

程序园 精品问答 技术交流 资源下载
返回列表 发新帖
首页 › 业界区 › 科技 ›算法day11-二叉树（1）

算法day11-二叉树（1）

挠溃症 昨天 10:19
目录


  • 二叉树理论基础
  • 二叉树递归遍历
  • 二叉树迭代遍历
  • 统一的迭代遍历方法
  • 小结
一、二叉树理论基础

　　种类：满二叉树（除了叶子节点外，每个节点都有两个子节点）、完全二叉树（每一层都被填满，最后一层从左到右连续排列）、二叉搜索树（左子树所有节点小于根节点，右子树所有节点大于根节点）、平衡二叉搜索树（在 BST 基础上增加了高度平衡限制，使查找效率更优）。
　　存储方式：

  • 1）顺序存储：用数组来存储。若父节点的数组下标是i，那么左孩子就是i*2+1，右孩子就是i*2+2。
  • 2）链式存储：
  1. class TreeNode{
  2.     int val;
  3.     TreeNode left;
  4.     TreeNode right;
  5.     TreeNode(int val){
  6.          this.val = val;      
  7.     }
  8. };
复制代码

  • 3）遍历方法：

    • 深度优先遍历：前序（递归、迭代）、中序（递归、迭代）、后序（递归、迭代）
    • 广度优先遍历：层序遍历（迭代法）

二、二叉树递归遍历

 　　写递归函数的三个步骤：

  • 确定参数和返回值
  • 写清终止条件：加个”停止递归“的判断，不然会无限调用导致程序崩溃。
  • 写好每一层要干啥
 1. 二叉树的前序遍历（根 → 左 → 右）

　　前序遍历是按照：根-左-右的顺序来访问。
  1. class Solution {
  2.     public List<Integer> preorderTraversal(TreeNode root) {
  3.         List<Integer> res = new ArrayList<>();
  4.         preorder(root, res);
  5.         return res;
  6.     }
  8.     public void preorder(TreeNode root, List<Integer> res){
  9.         if(root == null){
  10.             return;
  11.         }
  12.         res.add(root.val);
  13.         preorder(root.left, res);
  14.         preorder(root.right, res);
  15.     }
  16. }
  17. //时间复杂度：O（n），其中 n 是二叉树的节点数。每一个节点恰好被遍历一次。
  18. //空间复杂度：O（n），平均情况为O（logn），最坏情况为O（n）
复制代码
 2. 二叉树的中序遍历（左 → 根 → 右）

　　适用于二叉搜索树，遍历结果是有序数组。
  1. class Solution{
  2.     public List<Integer> inorderTraversal(TreeNode root){
  3.         List<Integer> res = new ArrayList<>();
  4.         inorder(root, res);
  5.         return res;
  6.     }
  8.     public void inorder(TreeNode root, List<Integer> res){
  9.         if(root == null){
  10.             return;
  11.         }
  12.         inorder(root.left, res);
  13.         res.add(root.val);
  14.         inorder(root.right, res);
  15.     }
  16. }
复制代码
 3. 二叉树的后序遍历（左 → 右 → 根）
  1. class Solution {
  2.     public List<Integer> postorderTraversal(TreeNode root) {
  3.         List<Integer> res = new ArrayList<>();
  4.         postorder(root, res);
  5.         return res;
  6.     }
  8.     public void postorder(TreeNode root, List<Integer> res){
  9.         if(root == null){
  10.             return;
  11.         }
  12.         postorder(root.left, res);
  13.         postorder(root.right, res);
  14.         res.add(root.val);
  15.     }
  16. }
复制代码
三、二叉树迭代遍历

　　迭代遍历主要使用 栈（Stack）来模拟递归过程，使得程序更具显式流程。
 1. 二叉树的前序遍历


  • 使用栈先处理左子树。
  • 每次访问当前节点后，将右子节点入栈，保证左子节点优先出栈。
  1. class Solution {
  2.     public List<Integer> preorderTraversal(TreeNode root) {
  3.         List<Integer> res = new ArrayList<>();
  4.         if(root == null){
  5.             return res;
  6.         }
  7.         Deque<TreeNode> stack = new LinkedList<>();
  8.         TreeNode node = root;
  9.         while(!stack.isEmpty() || node != null){
  10.             while(node != null){
  11.                 res.add(node.val);
  12.                 stack.push(node);
  13.                 node = node.left;
  14.             }
  15.             node = stack.pop();
  16.             node = node.right;
  17.         }
  18.         return res;
  19.     }
  20. }
  21. //时间复杂度：O(n)
  22. //空间复杂度：O(n)
复制代码
 2. 二叉树的中序遍历


  • 使用栈一直向左深入，直到最左叶子。
  • 退栈访问当前节点，再右移。
  1. class Solution{
  2.     public List<Integer> inorderTraversal(TreeNode root){
  3.         List<Integer> res = new ArrayList<>();
  4.         if(root == null){
  5.             return res;
  6.         }
  7.         Deque<TreeNode> stack = new LinkedList<>();
  8.         TreeNode node = root;
  9.         while(!stack.isEmpty() || node!=null){
  10.             while(node != null){
  11.                 stack.push(node);
  12.                 node = node.left;
  13.             }
  14.             node = stack.pop();
  15.             res.add(node.val);
  16.             node = node.right;
  17.         }
  18.         return res;
  19.     }
  20. }
复制代码
 3. 二叉树的后序遍历


  • 较为复杂，需记录“上一次访问的节点”prev，判断右子树是否处理过。
  • 若右子树尚未处理，需要先压栈等待右子树遍历完成。
  1. class Solution {
  2.     public List<Integer> postorderTraversal(TreeNode root) {
  3.         List<Integer> res = new ArrayList<>();
  4.         if(root == null){
  5.             return res;
  6.         }
  7.         Deque<TreeNode> stack = new LinkedList<>();
  8.         TreeNode prev = null;
  9.         while(root != null || !stack.isEmpty()){
  10.             //先处理左边的所有节点（相对）
  11.             while(root != null){
  12.                 stack.push(root);
  13.                 root = root.left;
  14.             }
  15.             root = stack.pop();     //从栈里弹出来一个
  16.             if(root.right == null || root.right == prev){       //如果右边没有节点或右边节点已被处理过
  17.                 res.add(root.val);
  18.                 prev = root;        //记录上一个处理过的节点
  19.                 root = null;        //这里主要是控制不用处理左边节点了
  20.             }else{
  21.                 stack.push(root);       //处理右边的节点
  22.                 root = root.right;
  23.             }
  24.         }
  25.         return res;
  26.     }
  27. }
  28. //时间复杂度：O（n）
  29. //空间复杂度：O（n） 
复制代码
四、二叉树层序遍历

　　层序遍历采用 队列（Queue） 实现，属于 广度优先搜索（BFS）。

  • 每一层入队一次，遍历队列中所有节点，将其子节点依次加入队列。
  • 可以通过 level.size() 控制当前层级的节点数量，确保按层处理。
　　　这个方法特别适合：求层数、最短路径；按层收集结果；广度相关题目（如最小深度、右视图等）。
[code]class Solution {    public List levelOrder(TreeNode root) {        List res = new ArrayList();        if(root == null){            return res;        }        Queue queue = new LinkedList();        queue.offer(root);        while(!queue.isEmpty()){            List level = new ArrayList();            int size = queue.size();            for(int i=0; i

使用道具 举报
相关推荐
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册
发帖
挠溃症
昨天 10:19

0

粉丝关注

12

主题发布

板块介绍填写区域，请于后台编辑
微信扫一扫