devbox
我家小花儿
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

剑指offerDayN树篇_treenode pre =null;与 treenode pre =new treenode()有

作者：我家小花儿 | 2024-05-20 04:09:01

赞

踩

treenode pre =null;与 treenode pre =new treenode()有什么区别

根据前序中序递归重建二叉树

  1. package offer;
  2.  
  3. import java.util.Arrays;
  4. import java.util.Stack;
  5.  
  6. class TreeNode {
  7.     int val;
  8.     TreeNode left;
  9.     TreeNode right;
  10.  
  11.     public TreeNode(int val) {
  12.         this.val = val;
  13.     }
  14. }
  15.  
  16. /*
  17. 前序中序重建二叉树
  18. Arrays.copyOfRange()
  19. 主要用于对一个已有的数组进行截取复制，复制出一个左闭右开区间的数组。
  20.  */
  21. public class Test31 {
  22.     //递归调用构建树
  23.     public static TreeNode reConstruct(int[] preOrder, int[] inOrder) {
  24.         //先判空
  25.         if (preOrder.length == 0 || preOrder == null) return null;
  26.         //构建二叉树
  27.         TreeNode root = new TreeNode(preOrder[0]);
  28.         //查找根节点在中序之间的位置下标 每次左子树 跟右子树范围会发生变化
  29.         int index = findIndex(preOrder, inOrder);
  30.         //递归左子树
  31.         //中序index其实就是他的长度
  32.         root.left = reConstruct(Arrays.copyOfRange(preOrder, 1, index + 1), Arrays.copyOfRange(inOrder, 0, index));
  33.         //递归右子树
  34.         root.right = reConstruct(Arrays.copyOfRange(preOrder, index + 1, preOrder.length), Arrays.copyOfRange(inOrder, index + 1, inOrder.length));
  35.  
  36.         return root;
  37.     }
  38.  
  39.     /**
  40.      * 根据前序中序查找每次的根节点对应的下标
  41.      *
  42.      * @param preOrder
  43.      * @param inOrder
  44.      * @return
  45.      */
  46.     public static int findIndex(int[] preOrder, int[] inOrder) {
  47.         //每次的根节点都是在变化的
  48.         int root = preOrder[0];
  49.         for (int i = 0; i < preOrder.length; i++) {
  50.             if (inOrder[i] == root)
  51.                 return i;
  52.         }
  53.         return -1;
  54.     }
  55.  
  56.     //二叉树前序遍历 非递归
  57.  
  58.     /**
  59.      * 用栈实现非递归
  60.      *
  61.      * @param root
  62.      */
  63.     public static void preOrder(TreeNode root) {
  64.         //先判空
  65.         if (root == null)
  66.             return;
  67.         Stack<TreeNode> stack = new Stack<>();
  68.         stack.push(root);
  69.         while (!stack.isEmpty()) {
  70.             TreeNode node = stack.pop();
  71.             System.out.print(node.val+" ");
  72.             if (node.right != null)
  73.                 stack.push(node.right);
  74.             if (node.left != null)
  75.                 stack.push(node.left);
  76.  
  77.         }
  78.     }
  79.  
  80.     public static void main(String[] args) {
  81.         int[] preOrder = new int[]{1, 2, 4, 7, 3, 5, 6, 8};
  82.         int[] inOrder = new int[]{4, 7, 2, 1, 5, 3, 8, 6};
  83.         TreeNode tree = reConstruct(preOrder, inOrder);
  84.         preOrder(tree);
  85.     }
  86. }

层序遍历+按照节点位置输出层序遍历

树递归专栏：1树的镜像 2树的高度  3是否为平衡二叉树

  1. package offer;
  2.  
  3. import java.util.ArrayList;
  4. import java.util.LinkedList;
  5. import java.util.List;
  6. import java.util.Queue;
  7.  
  8. /*
  9. 1从上到下层序遍历树
  10. 2按照节点个数遍历树
  11. 3 二叉树镜像 对二叉树进轴对称
  12.     先对左右子树镜像
  13.     再对子树里面的数值进行求镜像
  14. 4求树的深度---递归经典套路
  15. 5判断树是不是平衡二叉树
  16.  */
  17. public class Test32 {
  18.     public static void bfsOrder(TreeNode root) {
  19.         //判空
  20.         if (root == null) return;
  21.         Queue<TreeNode> queue = new LinkedList<>();
  22.         queue.add(root);
  23.         while (!queue.isEmpty()) {
  24.             TreeNode node = queue.poll();
  25.             System.out.print(node.val + " ");
  26.             if (node.left != null)
  27.                 queue.add(node.left);
  28.             if (node.right != null)
  29.                 queue.add(node.right);
  30.         }
  31.     }
  32.  
  33.     /**
  34.      * 按照每行有多少节点返回
  35.      *
  36.      * @param root
  37.      */
  38.     public static List<List<Integer>> bfsOrder2(TreeNode root) {
  39.         //判空
  40.         if (root == null) return null;
  41.         List<List<Integer>> lists = new ArrayList<>();
  42.         Queue<TreeNode> queue = new LinkedList<>();
  43.         queue.add(root);
  44.  
  45.         while (!queue.isEmpty()) {
  46.             int size = queue.size();
  47.             //每次新建一个列表
  48.             List<Integer> temp = new ArrayList<>();
  49.             while (size-- > 0) {
  50.                 TreeNode node = queue.poll();
  51.                 temp.add(node.val);
  52.                 if (node.left != null)
  53.                     queue.add(node.left);
  54.                 if (node.right != null)
  55.                     queue.add(node.right);
  56.             }
  57.             lists.add(temp);
  58.         }
  59.         return lists;
  60.     }
  61.  
  62.     /**
  63.      * 递归
  64.      * 先对左右子树镜像
  65.      * 再对子树里面的数值进行求镜像
  66.      *
  67.      * @param root
  68.      * @return
  69.      */
  70.     public static TreeNode mirrorTree(TreeNode root) {
  71.         if (root == null) return null;
  72.         //递归翻转子节点
  73.         //定义零时变量 右边放到左边 然后再把左边放到右边
  74.         TreeNode temp = root.left;
  75.         root.left = mirrorTree(root.right);
  76.         root.right = mirrorTree(temp);
  77.         return root;
  78.  
  79.         /*
  80.         写的复杂点
  81.         获得翻转子树
  82.         TreeNode l = mirrorTree(root.left);
  83.         TreeNode r = mirrorTree(root.right);
  84.         子树互换
  85.         root.left = l;
  86.         root.right = r;
  87.         return root;
  88.          */
  89.     }
  90.  
  91.     /**
  92.      * 递归求二叉树的高度
  93.      * 返回左右子树的高度加1
  94.      *
  95.      * @param root
  96.      * @return
  97.      */
  98.     public static int maxDepth(TreeNode root) {
  99.         if (root == null) return 0;
  100.         int l = maxDepth(root.left);
  101.         int r = maxDepth(root.right);
  102.         return l > r ? l + 1 : r + 1;
  103.     }
  104.  
  105.     //平衡二叉树 任意节点的左右子树的高度不相差1 就是平衡二叉树
  106.  
  107.     /**
  108.      * r任意节点
  109.      * 高度相差1
  110.      *
  111.      * @param root
  112.      * @return
  113.      */
  114.     public static boolean isBinarayTree(TreeNode root) {
  115.         if (root == null) return true;
  116.         //先求根节点左右两边子树的的深度差
  117.         int l = maxDepth(root.left);
  118.         int r = maxDepth(root.right);
  119.         //|l-1|<=1
  120.         //并且递归左右子树差都不能大于1
  121.         return l - r >= -1 && l - r <= 1 && isBinarayTree(root.left) && isBinarayTree(root.right);
  122.     }
  123.  
  124.     public static void main(String[] args) {
  125. //构建一颗树
  126.         TreeNode node6 = new TreeNode(6, null, null);
  127.         TreeNode node5 = new TreeNode(5, null, null);
  128.         TreeNode node4 = new TreeNode(4, null, null);
  129.         TreeNode node3 = new TreeNode(3, node6, null);
  130.         TreeNode node2 = new TreeNode(2, node4, node5);
  131.         TreeNode node1 = new TreeNode(1, node2, node3);
  132.         bfsOrder(node1);
  133.         System.out.println(bfsOrder2(node1));
  134.         System.out.println();
  135.         mirrorTree(node1);
  136.         System.out.println(bfsOrder2(node1));
  137.         System.out.println(maxDepth(node1));
  138.         System.out.println(isBinarayTree(node1));
  139.     }
  140. }

三种层序遍历的方式

  1. package offer;
  2.  
  3. import java.util.LinkedList;
  4. import java.util.List;
  5. import java.util.Queue;
  6.  
  7. /*
  8. 二叉树的打印
  9. 从上到下打印二叉树
  10. 1从上到下层序遍历
  11. 2分层打印
  12. 3之子形打印   特点 用linkedlist  头部插入比arraylist快很多
  13.  */
  14. public class Test33 {
  15.     //基础的层序遍历bfs
  16.     public static void bfsOrders(TreeNode root) {
  17.         //判空
  18.         if (root == null) return;
  19.         Queue<TreeNode> queue = new LinkedList<>();
  20.         queue.add(root);
  21.         while (!queue.isEmpty()) {
  22.             TreeNode node = queue.poll();
  23.             System.out.print(node.val + " ");
  24.             if (node.left != null)
  25.                 queue.add(node.left);
  26.             if (node.right != null)
  27.                 queue.add(node.right);
  28.         }
  29.     }
  30.  
  31.     //按照每层的节点内容输出
  32.     public static List<List<Integer>> bfsOrders2(TreeNode root) {
  33.         //判空
  34.         if (root == null) return null;
  35.         Queue<TreeNode> queue = new LinkedList<>();
  36.         List<List<Integer>> list = new LinkedList<>();
  37.         queue.add(root);
  38.         while (!queue.isEmpty()) {
  39.             int size = queue.size();
  40.             List<Integer> temp = new LinkedList<>();
  41.             while (size-- > 0) {
  42.                 TreeNode node = queue.poll();
  43.                 temp.add(node.val);
  44.                 if (node.left != null)
  45.                     queue.add(node.left);
  46.                 if (node.right != null)
  47.                     queue.add(node.right);
  48.             }
  49.             list.add(temp);
  50.         }
  51.         return list;
  52.     }
  53.  
  54.     //z形输出树的节点
  55.     //奇数在队列后面添加 偶数在队里前面添加
  56.  
  57.     /**
  58.      * 队列前面添加 queue.add(0,node.val)
  59.      *添加flag指标 判断
  60.      * @param root
  61.      */
  62.     public static List<List<Integer>> bfsOrders3(TreeNode root) {
  63.         //判空
  64.         if (root == null) return null;
  65.         Queue<TreeNode> queue = new LinkedList<>();
  66.         List<List<Integer>> list = new LinkedList<>();
  67.         queue.add(root);
  68.         //每次输出一层
  69.         //设置标识flag flag为true则添加
  70.         boolean flag = true;
  71.         while (!queue.isEmpty()) {
  72.             int size = queue.size();
  73.             List<Integer> temp = new LinkedList<>();
  74.             while (size-->0){
  75.                 TreeNode node = queue.poll();
  76.                 if (flag) temp.add(node.val);// 从左往右
  77.                 else temp.add(0, node.val);//奇数从右往左
  78.                 if (node.left != null)
  79.                     queue.add(node.left);
  80.                 if (node.right != null)
  81.                     queue.add(node.right);
  82.             }
  83.             flag = !flag;
  84.             list.add(temp);
  85.         }
  86.         return list;
  87.     }
  88.  
  89.     public static void main(String[] args) {
  90.         TreeNode node6 = new TreeNode(6, null, null);
  91.         TreeNode node5 = new TreeNode(5, null, null);
  92.         TreeNode node4 = new TreeNode(4, null, null);
  93.         TreeNode node3 = new TreeNode(3, node6, null);
  94.         TreeNode node2 = new TreeNode(2, node4, node5);
  95.         TreeNode node1 = new TreeNode(1, node2, node3);
  96.         bfsOrders(node1);
  97.         System.out.println();
  98.         System.out.println(bfsOrders2(node1));
  99.         System.out.println(bfsOrders3(node1));
  100.     }
  101. }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家小花儿/article/detail/596047
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号