数据结构——二叉树经典习题讲解

 各位看官早安午安晚安呀

如果您觉得这篇文章对您有帮助的话

欢迎您一键三连，小编尽全力做到更好
欢迎您分享给更多人哦

大家好，我们今天来学习java数据结构的二叉树

递归很重要的一些注意事项：

  • 1：递归你能不能掌握在于：你能不能想清楚第一层非递归 以及 递归结束的条件（也就是最后一层递归，有时候递归结束的条件可能有好几个这很常见）（结束的条件仔细想一下是否能够合并呢？return root，return null，下一层root啥也没干，root == null，是否能够合并呢？这个其实无伤大雅，但是能合并尽量还是合并一下）（这两个场景你能够想清楚，你基本思路就没什么问题）
  • 2：递归有返回值的
  • 2.1：如果有返回值，你大概率是要接收你下一层递归的返回值（）（然后你进行整理完之后继续向上返回）
  • 2.2：递归如果返回值是要叠加的，譬如求二叉树的高度的，这个返回值一定要接收。

1.1.判断两个二叉树是否相等

链接

  1.  public boolean isSameTree(TreeNode p, TreeNode q) {
  2.  
  3.         if(p == null && q != null || p != null && q == null){ //结构不一样不相等
  4.             return false;
  5.         }
  6.         if(p == null && q == null){ // 看你俩只要同时为空就相等
  7.             return true;
  8.         }
  9.  
  10.         return p.val == q.val && isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
  11.         
  12.     }

1.2.相同的二叉树

相同的树

  1. public boolean isSameTree(TreeNode p, TreeNode q) {
  2.  
  3.         if(p == null && q != null || p != null && q == null){
  4.             return false;
  5.         }
  6.         if(p == null && q == null){
  7.             return true;
  8.         }
  9.  
  10.         return p.val == q.val && isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
  11.         
  12.     }
  13.     public boolean isSubtree(TreeNode root, TreeNode subRoot) {
  14.         if(isSameTree(root,subRoot)){ //判断一开始就是否相等
  15.             return true;
  16.         }
  17.         if(root == null){
  18.             return false;
  19.         }
  20.         if(isSubtree(root.left,subRoot) ||  isSubtree(root.right,subRoot)){ //左边和右边一个相等就行
  21.         //其实这个就是前序遍历，利用返回值
  22.             return true;
  23.         }
  24.         return false;
  25.     }

1.3.翻转二叉树

翻转二叉树

  1. public TreeNode invertTree(TreeNode root) {
  2.         if(root == null){
  3.             return null;
  4.         }
  5.        
  6.         //交换节点
  7.         TreeNode tmp = root.left;
  8.         root.left = root.right;
  9.         root.right = tmp;
  10.  
  11. //翻转
  12.         invertTree(root.left);
  13.         invertTree(root.right);
  14.  
  15.         return root;
  16.         
  17.     }

1.4.平衡二叉树

平衡二叉树

补充知识点:

  1.  //更改的平衡二叉树，因为我们在算高度的时候每一颗子树的高度我们都算过,我们完全可以算整个树的高度
  2.     //然后进行顺带算两边的高度差是否 <= 1,一次性算完
  3.     int getHeight2(TreeNode root){
  4.         if(root == null){
  5.             return 0;
  6.         }
  7.         //左树高度和右树高度
  8.         int leftHeight = getHeight2(root.left);
  9.         int rightHeight = getHeight2(root.right);
  10.        //两边高度差<= 1并且都大于0（任何一个高度为-1的时候，整个树的返回值就为-1（-1代表不平衡））
  11.        //  只要有一个-1返回，那么之后都是返回-1，不平衡
  12.         if(Math.abs(leftHeight - rightHeight) <= 1 &&  leftHeight >= 0 && rightHeight >= 0){
  13.             return Math.max(leftHeight,rightHeight)+1;
  14.         }
  15.         return -1;
  16.     }
  17.     
  18.     public boolean isBalanced(TreeNode root) {
  19.         if(root == null){
  20.             return true;
  21.         }     
  22.         return  getHeight2(root) >= 0;
  23.     }

1.5.对称二叉树

对称二叉树

  1. public boolean isSymmetric(TreeNode root) {
  2.         if(root == null){
  3.             return true;
  4.         }
  5.         //我要看是否对称，肯定要两个节点进行比较，要两个变量
  6.        
  7.         return isSample(root.left,root.right);
  8.     }
  9.         
  10.  
  11.     public boolean isSample(TreeNode p , TreeNode q){
  12.         //两边都是空的，就一个根，直接返回true
  13.         if( p == null && q == null){
  14.             return true;
  15.         }
  16.         //一个为空另一个不为空，直接返回false
  17.         if( p == null || q == null){
  18.             return false;
  19.         }
  20.         if(p.val != q.val){
  21.             return false;
  22.         }
  23.         return isSample(p.left,q.right) && isSample(p.right,q.left);
  24.     }

1.6.通过字符串构建二叉树

通过字符串构建二叉树

  1. import java.util.Scanner;
  2. class TreeNode{
  3.     char val;
  4.     TreeNode left;
  5.     TreeNode right;
  6.     public TreeNode(){
  7.  
  8.     }
  9.     public TreeNode(char val){
  10.         this.val = val;
  11.     }
  12. }
  13.  
  14. // 注意类名必须为 Main, 不要有任何 package xxx 信息
  15. public class Main {
  16.     public static void main(String[] args) {
  17.         Scanner in = new Scanner(System.in);
  18.         // 注意 hasNext 和 hasNextLine 的区别
  19.         while (in.hasNextLine()) { // 注意 while 处理多个 case
  20.             String str = in.nextLine();
  21.             //创建二叉树
  22.             TreeNode root = create(str);
  23.              //中序遍历
  24.             inorder(root);
  25.         }
  26.     }
  27.  
  28.     public static int i = 0;
  29.     public static TreeNode create(String str){  //递归的第一层要素就是要知道什么时候结束
  30.     // 首先我们遇到 “#” 就要返回 ,但是我们的i还是要先++  后返回
  31.     if(str.charAt(i) == '#'){//但是我们要考虑的是，我们就算是返回了，我们的遍历str的i还是要往前走
  32.         i++;
  33.         return null;
  34.     }else{
  35.         TreeNode root = new TreeNode(str.charAt(i));
  36.         i++;
  37.         root.left = create(str);
  38.         root.right = create(str);
  39.         return root;
  40.     }
  41. //最后你会发现其实这两个返回值可以合并成一个，//其实每次递归题大家都可以看一下
  42.     }
  43.  
  44. //中序遍历
  45.     public static void inorder(TreeNode root){
  46.     if(root == null){
  47.         return;
  48.     }
  49.     inorder(root.left);
  50.     System.out.print(root.val +" ");
  51.     inorder(root.right);
  52.     }
  53. }

1.7.二叉树分层遍历：

二叉树的层序遍历

  1. public List> levelOrder(TreeNode root) {
  2.         List> list = new ArrayList<>();//别问 问就是OJ的测试用例让我这么干的
  3.         // root = []  预期结果[]，所以下面返回的也是List而不是null
  4.         if(root == null){ //如果根节点都是null，就不用遍历了
  5.             return list;
  6.         }
  7.         
  8.         // 先把 根节点add进去队列里面
  9.         Queue queue = new LinkedList<>();
  10.         queue.offer(root);
  11.         //tmp.add(root);//这里不对呀，最后一倍一倍的增长。这个size也不对，看我下面如何修改
  12.         while(!queue.isEmpty()) {
  13.             //int size = tmp.size();
  14.             List tmp = new ArrayList<>();//这个可不敢放在一开始呀，不然又叠加了(ArrayList好一点)
  15.             int size = queue.size();//计算上一次add进来的总和， 下面直接就是  size!=0,这完全就是要把上一次的全poll出去
  16.             while (size != 0) {     //和上一个的区别就在于，上一个层序遍历是一个一个出队列的，这个是一次性把上一次add进来的全部poll出去
  17.                 TreeNode cur = queue.poll();
  18.                 tmp.add(cur.val);
  19.                // System.out.println(cur.val + " ");
  20.                 size--;//记得--;
  21.                 if (cur.left != null) {
  22.                     queue.offer(cur.left);
  23.                 }
  24.                 if (cur.right != null) {
  25.                     queue.offer(cur.right);
  26.                 }
  27.             }
  28.             list.add(tmp);
  29.         }
  30.         return list;
  31.     }

1.8.二叉树的最近公共祖先

二叉树的最近公共祖先

  1.  public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
  2.          if(p == root || q == root){
  3.             return root;
  4.         }
  5.         if(root == null){
  6.             return null;
  7.         }
  8.         TreeNode leftRoot = lowestCommonAncestor(root.left,p,q);
  9.         TreeNode rightRoot = lowestCommonAncestor(root.right,p,q);
  10.         if(leftRoot != null && rightRoot != null){
  11.             return root;
  12.         } else if (leftRoot != null) {
  13.             return leftRoot;
  14.         }else{
  15.             return rightRoot;
  16.         }
  17.     }

解法二：看成两个链表相交，找相交点

  1. private boolean getPath(TreeNode root,TreeNode node,Stackstack){
  2.         // 判断这个节点是不是这个路径上的节点(如果不是，看看它的左子树和右子树是不是这个路径上的节点如果都不是)
  3.         //就返回false，把这个节点pop出来
  4.         if(root == null || node == null){
  5.             return false;
  6.         }
  7.         stack.push(root);
  8.         //一定要压进去，不然root == node 导致这个栈里面没有了元素
  9.         if(root == node){
  10.             return true;
  11.         }
  12.         boolean flg1 = getPath(root.left,node,stack);
  13.         //看看左节点有没有
  14.         if(flg1){
  15.             return true;
  16.         }
  17.         boolean flg2 = getPath(root.right,node,stack);
  18.         //看看右节点有没有
  19.         if(flg2){
  20.             return true;
  21.         }
  22.         //都没有就return false
  23.         stack.pop();
  24.         return false;
  25.     }
  26.     public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
  27.         Stackstack1 = new Stack<>();
  28.         Stackstack2 = new Stack<>();
  29.         //利用getPath初始化这两个栈
  30.         getPath(root,p,stack1);
  31.         getPath(root,q,stack2);
  32.         //初始化之后，进行比较，让长栈先走size步
  33.         int size = stack1.size() -stack2.size();
  34.         if(size > 0){
  35.             while(size != 0){
  36.                 stack1.pop();
  37.                 size--;
  38.             }
  39.         }else{
  40.             while(size != 0){
  41.                 stack2.pop();
  42.                 size++;
  43.             }
  44.         }
  45.         while(!stack1.isEmpty() && ! stack2.isEmpty()){ //&&后面的写不写都行
  46.             if(stack1.peek().equals(stack2.peek())){
  47.                 return stack1.peek();
  48.             }
  49.             stack1.pop();
  50.             stack2.pop();
  51.         }
  52.         return null;
  53.     }

1.9. 从前序与中序遍历序列构造二叉树

 从前序与中序遍历序列构造二叉树

  1. class Solution {
  2.     public int preIndex;//一定要设置成成员变量（全局效果），局部变量的话放方法参数里，每次都是传值调用
  3.     //不能保证preIndex一直往前走
  4.     public TreeNode buildTree(int[] preorder, int[] inorder) {
  5.  
  6.         return buildTreeChild(preorder,inorder,0,inorder.length -1);
  7.  
  8.     }
  9.     private TreeNode buildTreeChild(int[] preorder,int[] inorder,int inbegin,int inend){
  10.         if(inbegin > inend ){  //其实这里的结束有两次，inbegin = inend 也应该结束（但是合并成一种情况了）
  11.             return null;
  12.         }
  13.         if(inbegin == inend){
  14.             int pre = preIndex;
  15.             preIndex++;
  16.            return new TreeNode(preorder[pre]);
  17.         }
  18.         //先看这个（前序遍历的）节点是否在中序遍历的这个范围内，在的话我再把这个根节点给创建出来
  19.         int rootIndex = findIndex(inorder,inbegin,inend,preorder[preIndex]);
  20.         if(rootIndex == -1){
  21.             return null;
  22.         }
  23.         TreeNode root = new TreeNode(preorder[preIndex]);
  24.         
  25.         preIndex++;
  26.         root.left = buildTreeChild(preorder,inorder,inbegin,rootIndex-1);
  27.         root.right = buildTreeChild(preorder,inorder,rootIndex + 1,inend);
  28.         return root;
  29.     }
  30.     private int findIndex(int[] inorder,int inbegin,int inend,int key){
  31.         for(int i = inbegin; i<= inend ; i++){
  32.             if(inorder[i] == key){
  33.                 return i;
  34.             }
  35.         }
  36.         return -1;
  37.     }
  38. }

1.10.从中序与后序遍历序列构造二叉树

如果后序：是先递归右树，再左树，再根（此刻的后序的字符串就是前序的逆转）

1从中序与后序遍历序列构造二叉树

  1. class Solution {
  2.     public int postIndex ;//一定要设置成成员变量（全局效果），局部变量的话放方法参数里，每次都是传值调用
  3.     //不能保证preIndex一直往前走
  4.     public TreeNode buildTree(int[] inorder, int[] postorder) {
  5.         postIndex = postorder.length -1;
  6.         return buildTreeChild(postorder,inorder,0,inorder.length -1);
  7.     }
  8.     private TreeNode buildTreeChild(int[] postorder,int[] inorder,int inbegin,int inend){
  9.         if(inbegin > inend ){  //其实这里的结束有两次，inbegin = inend 也应该结束（但是合并成一种情况了）
  10.             return null;
  11.         }
  12.         
  13.         //先看这个（前序遍历的）节点是否在中序遍历的这个范围内，在的话我再把这个根节点给创建出来
  14.         int rootIndex = findIndex(inorder,inbegin,inend,postorder[postIndex]);
  15.         if(rootIndex == -1){
  16.             return null;
  17.         }
  18.         TreeNode root = new TreeNode(postorder[postIndex]);
  19.         
  20.         postIndex--;
  21.         
  22.         root.right = buildTreeChild(postorder,inorder,rootIndex + 1,inend);
  23.         root.left = buildTreeChild(postorder,inorder,inbegin,rootIndex-1);
  24.         return root;
  25.     }
  26.     private int findIndex(int[] inorder,int inbegin,int inend,int key){
  27.         for(int i = inbegin; i<= inend ; i++){
  28.             if(inorder[i] == key){
  29.                 return i;
  30.             }
  31.         }
  32.         return -1;
  33.     }
  34. }

1.11.前序遍历二叉树（迭代实现）

  1.  public static void preOrder1(TreeNode root) {
  2.         if (root == null) {
  3.             return;
  4.         }
  5.         //本质上这还是递归的思想（stack还是往回走，不然你路上的节点，没办法遍历他的右边；
  6.         Stack stack = new Stack<>();
  7.         TreeNode cur = root;
  8.         while (cur != null || !stack.isEmpty()) {// 加个cur !=null,纯粹是因为，第一次stack是空的
  9.             while (cur != null) {//一直往
  10.                 System.out.print(cur.val);
  11.                 stack.push(cur);
  12.                 cur = cur.left;
  13.                 //其实一开始我是这么想的
  14.             /*if(cur == null){
  15.                 cur = stack.pop();
  16.                 cur = cur.right;
  17.                 //但是这样就废了呀，右边为空就完蛋了，循环结束，gameOver
  18.             }*/
  19.             }
  20.             //左边为空，直接就拿回我上一个根，然后打印右边
  21.             cur = stack.pop();
  22.             cur = cur.right;
  23.         }
  24.     }

1.11.中序遍历二叉树（迭代实现）

  1. public static void inOrder1(TreeNode root) {
  2.         if (root == null) {
  3.             return;
  4.         }
  5.         //本质上这还是递归的思想（stack还是往回走，不然你路上的节点，没办法遍历他的右边；
  6.         Stack stack = new Stack<>();
  7.         TreeNode cur = root;
  8.         while (cur != null || !stack.isEmpty()) {// 加个cur !=null,纯粹是因为，第一次stack是空的
  9.             while (cur != null) {//一直往
  10.                 stack.push(cur);
  11.                 cur = cur.left;
  12.             }
  13.             //左边为空，直接就拿回我上一个根，然后打印右边
  14.             cur = stack.pop();
  15.             System.out.print(cur.val);
  16.             cur = cur.right;
  17.         }
  18.     }

1.11.后序遍历二叉树（迭代实现）

  1.   //根据字符串循环进行后序遍历
  2.     public static void postOrder1(TreeNode root) {
  3.         if (root == null) {
  4.             return;
  5.         }
  6.         //本质上这还是递归的思想（stack还是往回走，不然你路上的节点，没办法遍历他的右边；
  7.         Stack stack = new Stack<>();
  8.         TreeNode cur = root;
  9.         TreeNode prev = null;
  10.         TreeNode top = null;
  11.         while (cur != null || !stack.isEmpty()) {// 加个cur !=null,纯粹是因为，第一次stack是空的
  12.             while (cur != null) {//一直往
  13.                 stack.push(cur);
  14.                 cur = cur.left;
  15.             }
  16.             //左边为空，直接就拿回我上一个根，然后打印右边
  17.              top = stack.peek();
  18.             if(top .right == null || top.right == prev){
  19.                 stack.pop();
  20.                 System.out.print(top.val + " ");
  21.                 prev = top;
  22.             }else {
  23.                 // 右边不为空不能pop
  24.                 cur = top.right;
  25.             }
  26.         }
  27.     }

上述就是二叉树习题讲解的全部内容了，能看到这里相信您一定对小编的文章有了一定的认可，二叉树的出现让我们对于数据的组织的利用有了更加方便的使用~~

有什么问题欢迎各位大佬指出
欢迎各位大佬评论区留言修正

您的支持就是我最大的动力​​​！！！！

注：本文转载自blog.csdn.net的郑州吴彦祖772的文章"https://blog.csdn.net/2302_80639556/article/details/143923032"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。
复制链接
相关推荐
发表评论

评论记录：

未查询到任何数据！