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

【数据结构】二叉树重点知识和OJ题汇总（附有代码）_oj 1109. 扩展二叉树

作者：寸_铁 | 2024-08-08 13:25:18

赞

踩

oj 1109. 扩展二叉树

目录

思维导图：​

1.树的概念：

2.二叉树：

3.二叉树的遍历：

4.二叉树的模拟实现：

5.二叉树的OJ题：

思维导图：

1.树的概念：

  1. 树是一种非线性的数据结构，由递归定义出来的。根节点R在上，其他节点在下；树形结构中子树不能有交集，否则不能称为树形结构。
  2. 树的几种重要概念，参照上图： 
    1.节点的度：一个节点含有子树的个数，例如：c的度就是3
2.树的度：一棵树中所有节点的度的最大值，例如：上图中树的度就是3
3.叶子节点或终端节点：一个节点没有任何子树，例如：j、k、e、f、g、m、n、i
4.双亲节点或父节点：一个节点含有子节点，例如：r是a、b、c的父节点
5.孩子节点或子节点：例如：a、b、c是r的孩子节点
6.根节点：一棵树中，没有双亲节点的节点，例如：r就是根节点
7.节点的层次：从根开始算，r为第1层，a、b、c为第2层
8.树的高度或深度：树中节点的最大层次，例如：上图中树的最大高度为4

2.二叉树：

  1. 二叉树是由1个根节点加上左子树和右子树组成的，每个根节点可以有2棵子树、1棵子树也可以没有子树。因此：二叉树不会存在度大于2的节点；二叉树的子树有左右之分，不可以颠倒；一颗二叉树的左子树和右子树也必须是二叉树。
  2. 有2种特殊的二叉树分别为满二叉树和完全二叉树。满二叉树是1棵二叉树上的每层节点数达到最大值，如果1棵二叉树的层数为n并且节点总数为 (2^n) - 1；则这棵树就是满二叉树。
  3. 二叉树的性质： 
    1.规定根节点的层数为1，则1棵非空二叉树的第i层上最多有2^(i-1)个节点
2.规定根节点的二叉树高度为1，则高度为k的二叉树最大节点数是2^k - 1
3.度为0的节点个数比度为2的个数多1个
4.有n个节点的完全二叉树的深度为log以2为底的(n+1)向上取整
  4. 二叉树的存储是通过一个一个的节点引用起来的，常用的表示方式有孩子表示法和孩子双亲表示法。二叉树的存储分为顺序存储和类似于链表的链式存储，注意类似于链表不是链表。

 

3.二叉树的遍历：

  1. 二叉树的遍历是二叉树最重要的基本功能。
  2. 前序遍历：先访问根节点—>左子树—>右子树 
    参照上图前序遍历：r a d e c g i
  3. 中序遍历：先访问左子树—>根节点—>右子树 
    参照上图中序遍历：d a e r g c i
  4. 后序遍历：先访问左子树—>右子树—>根节点 
    参照上图后序遍历：d e a g i c r
  5. 层序遍历：从左到右遍历每一层 
    参照上图层序遍历：r a c d e g i
  6. 根据前序遍历和后序遍历不能创建出一个二叉树，前序和后序只能确定根。
  7. 前、中、后、层+序遍历的代码实现：
  1. public class BinaryTree {
  2.     class TreeNode{
  3.         //孩子表示法
  4.         public char val;
  5.         public TreeNode left;
  6.         public TreeNode right;
  7.         public TreeNode(char val){
  8.             this.val = val;
  9.         }
  10.     }
  11.     public TreeNode root;
  12.  
  13.     //前序遍历1
  14.     public void preOrder1(TreeNode root){
  15.         if(root == null) return;
  16.         System.out.print(root.val+" ");
  17.         preOrder1(root.left);
  18.         preOrder1(root.right);
  19.     }
  20.     //前序遍历2：有返回值类型，遍历思路
  21.     class Solution{
  22.         //list必须定义在外面，否则每次递归都会创建1个list
  23.         List<Character> list = new ArrayList<>();
  24.         public List<Character> preOrder2(TreeNode root){
  25.             if(root == null) return list;
  26.             list.add(root.val);
  27.             preOrder2(root.left);
  28.             preOrder2(root.right);
  29.             return list;
  30.         }
  31.     }
  32.     //前序遍历3：有返回值，子问题思路
  33.     public List<Character> preOrder3(TreeNode root){
  34.         List<Character> list = new ArrayList<>();
  35.         if(root == null) return list;
  36.         list.add(root.val);
  37.         List<Character> leftTree = preOrder3(root.left);
  38.         list.addAll(leftTree);
  39.         List<Character> rightTree = preOrder3(root.right);
  40.         list.addAll(rightTree);
  41.         return list;
  42.     }
  43.  
  44.  
  45.     //中序遍历1
  46.     public void inOrder(TreeNode root){
  47.         if(root == null) return;
  48.         inOrder(root.left);
  49.         System.out.print(root.val+" ");
  50.         inOrder(root.right);
  51.     }
  52.     //中序遍历2：有返回值，子问题思路
  53.     public List<Character> inOrder2(TreeNode root){
  54.         List<Character> list = new ArrayList<>();
  55.         if(root == null) return list;
  56.         List<Character> leftTree = inOrder2(root.left);
  57.         list.addAll(leftTree);
  58.  
  59.         list.add(root.val);
  60.  
  61.         List<Character> rightTree = inOrder2(root.right);
  62.         list.addAll(rightTree);
  63.         return list;
  64.     }
  65.     
  66.     //后序遍历1
  67.     public void postOrder(TreeNode root){
  68.         if(root == null) return;
  69.         postOrder(root.left);
  70.         postOrder(root.right);
  71.         System.out.print(root.val+" ");
  72.     }
  73.     //后序遍历2：有返回值，子问题思路
  74.     public List<Character> postOrder2(TreeNode root){
  75.         List<Character> list = new ArrayList<>();
  76.         if(root == null) return list;
  77.         List<Character> leftTree = postOrder(root.left);
  78.         list.addAll(leftTree);
  79.  
  80.         List<Character> rightTree = postOrder2(root.right);
  81.         list.addAll(rightTree);
  82.         
  83.         list.add(root.val);
  84.  
  85.         return list;
  86.     }
  87.  
  88.     //层序遍历1:使用到了队列
  89.     public void levelOrder(TreeNode root){
  90.         if(root == null) return;
  91.         Queue<TreeNode> queue = new LinkedList<>();
  92.         queue.offer(root);
  93.         while(!queue.isEmpty()){
  94.             TreeNode cur = queue.poll();
  95.             System.out.print(cur+" ");
  96.             if(cur.left != null){
  97.                 queue.offer(cur.left);
  98.             }
  99.             if(cur.right != null){
  100.                 queue.offer(cur.right);
  101.             }
  102.         }
  103.     }
  104. }

 

4.二叉树的模拟实现：

获取树中节点得个数

 获取叶子节点的个数

 获取第k层节点的个数

 获取二叉树的高度

 检测值value是否存在

 代码实现如下：

  1. public class BinaryTree {
  2.     class TreeNode{
  3.         //孩子表示法
  4.         public char val;
  5.         public TreeNode left;
  6.         public TreeNode right;
  7.         public TreeNode(char val){
  8.             this.val = val;
  9.         }
  10.     }
  11.     public TreeNode root;
  12.  
  13.     //获取树中节点的个数1:子问题思路
  14.     public int size(TreeNode root){
  15.         if(root == null) return 0;
  16.         return size(root.left)+size(root.right)+1;
  17.     }
  18.     //获取树中节点的个数2:遍历思路
  19.     public static int nodeSize;
  20.     public void size2(TreeNode root){
  21.         if(root == null) return;
  22.         nodeSize++;
  23.         size2(root.left);
  24.         size2(root.right);
  25.     }
  26.  
  27.     //获取叶子节点的个数1：子问题思路
  28.     public int getLeafNodeCount(TreeNode root){
  29.         if(root == null) return 0;
  30.         if(root.left == null && root.right==null){
  31.             return 1;
  32.         }
  33.         return getLeafNodeCount(root.left)+
  34.                     getLeafNodeCount(root.right);
  35.     }
  36.     //获取叶子节点的个数2：遍历思路
  37.     public static int leafSize;
  38.     public void getLeafNodeCount2(TreeNode root){
  39.         if(root == null) return;
  40.         if(root.left == null && root.right == null){
  41.             leafSize++;
  42.         }
  43.         getLeafNodeCount2(root.left);
  44.         getLeafNodeCount2(root.right);
  45.     }
  46.  
  47.     //获取第k层节点的个数：子问题思路
  48.     public int getKLevelNodeCount(TreeNode root,int k){
  49.         if(root == null) return 0;
  50.         if(k == 1) return 1;
  51.         //对k操作不会影响右树
  52.         return getKLevelNodeCount(root.left,k-1)
  53.                     +getKLevelNodeCount(root.right,k-1);
  54.     }
  55.  
  56.     //获取二叉树的高度
  57.     public int getHeight(TreeNode root){
  58.         if(root == null) return 0;
  59.         int leftHeight = getHeight(root.left);
  60.         int rightHeight = getHeight(root.right);
  61.         return (leftHeight > rightHeight?
  62.                             leftHeight+1 : rightHeight+1);
  63.     }
  64.  
  65.     //检测value是否存在
  66.     public TreeNode find(TreeNode root,int value){
  67.         if(root == null) return null;
  68.         if(root.val == value){
  69.             return root;
  70.         }
  71.         TreeNode ret1 = find(root.left,value);
  72.         if(ret1 != null) return ret1;
  73.         TreeNode ret2 = find(root.right,value);
  74.         if(ret2 != null) return ret2;
  75.  
  76.         return null;
  77.     }
  78.  
  79.     //判断一棵树是不是完全二叉树
  80.     public boolean isCompleteTree(TreeNode root){
  81.         if(root == null) return true;
  82.         Queue<TreeNode> queue = new LinkedList<>();
  83.         queue.offer(root);
  84.         while(!queue.isEmpty()){
  85.             TreeNode cur = queue.poll();
  86.             System.out.println(cur+" ");
  87.             if(cur != null){
  88.                 queue.offer(cur.left);
  89.                 queue.offer(cur.right);
  90.             }else{
  91.                 break;
  92.             }
  93.         }
  94.         while(!queue.isEmpty()){
  95.             TreeNode cur = queue.peek();
  96.             if(cur != null){
  97.                 return false;
  98.             }else{
  99.                 queue.poll();
  100.             }
  101.         }
  102.         return true;
  103.     }
  104.  
  105. }

5.二叉树的OJ题：

1.检查俩颗二叉树是否完全相同，时间复杂度为O(min(m,n))

  1. //检查俩颗树是否完全相同
  2. public boolean isSameTree(TreeNode p,TreeNode q){
  3.     if(p == null &&q != null || q == null && p != null) return false;
  4.     if(p == null && q == null) return true;
  5.     if(p.val == q.val) return true;
  6.  
  7.     return isSameTree(p.left,q.left) &&
  8.             isSameTree(p.right,q.right);
  9. }

2.判断一棵树是不是另外一棵树的子树，时间复杂度为O(m*n)

  1. //判断一棵树是不是另外一棵树的子树
  2. public boolean isSubTree(TreeNode root,TreeNode subRoot){
  3.     if(root == null || subRoot == null)  return false;
  4.  
  5.     if(isSameTree(root,subRoot)) return true;
  6.  
  7.     if(isSameTree(root.left,subRoot)) return true;
  8.  
  9.     if(isSameTree(root.right,subRoot)) return true;
  10.  
  11.     return false;
  12. }

3.二叉树的最大深度

  1. //得到一棵树的高度
  2. private int getHeight(TreeNode root) {
  3.     if(root == null) return 0;
  4.     int leftTree = getHeight(root.left);
  5.     int rightTree = getHeight(root.right);
  6.  
  7.     return leftTree > rightTree?
  8.                 leftTree+1 : rightTree+1;
  9. }

4.判断一棵树是不是平衡二叉树

  1. //得到一棵树的高度
  2. private int getHeight(TreeNode root) {
  3.     if(root == null) return 0;
  4.     int leftTree = getHeight(root.left);
  5.     int rightTree = getHeight(root.right);
  6.  
  7.     return leftTree > rightTree?
  8.                 leftTree+1 : rightTree+1;
  9. }
  10. //1.判断一棵树是否是平衡二叉树,时间复杂度为O(n^2)
  11. public boolean isBalanced(TreeNode root){
  12.     if(root == null){
  13.         return true;
  14.     }
  15.     int leftTree = getHeight(root.left);
  16.     int rightTree = getHeight(root.right);
  17.  
  18.     return Math.abs(leftTree-rightTree)<=1
  19.             && isBalanced(root.left)
  20.             && isBalanced(root.right);
  21. }
  22.  
  23. //2.判断一棵树是否是平衡二叉树，时间复杂度为O(n)
  24. public boolean isBalanced2(TreeNode root){
  25.     if(root == null) return true;
  26.     return maxDepth(root)>=0;
  27. }
  28. private int maxDepth(TreeNode root) {
  29.     if(root == null) return 0;
  30.     int leftTree = maxDepth(root.left);
  31.     int rightTree = maxDepth(root.right);
  32.     if(leftTree >= 0 && rightTree >= 0 && Math.abs(leftTree-rightTree) <= 1){
  33.         return Math.max(leftTree,rightTree)+1;
  34.     }else{
  35.         return -1;
  36.     }
  37. }

5.构建一颗二叉树

  1. //构建一颗二叉树
  2. public static int i;
  3. public TreeNode createTree(String s){
  4.     TreeNode root = null;
  5.     if(s.charAt(i) != '#'){
  6.         root = new TreeNode(s.charAt(i));
  7.         i++;
  8.         root.left = createTree(s);
  9.         root.right = createTree(s);
  10.     }else{
  11.         i++;
  12.     }
  13.  
  14.     return root;
  15. }

6.二叉树的分层遍历

  1. //二叉树的分层遍历
  2. public List<List<Character>> levelOrder(TreeNode root){
  3.     List<List<Character>> ret = new ArrayList<>();
  4.  
  5.     if(root == null) return ret;
  6.     Queue<TreeNode> queue = new LinkedList<>();
  7.     queue.offer(root);
  8.     while(!queue.isEmpty()){
  9.         int size = queue.size();
  10.         List<Character> row = new ArrayList<>();
  11.         while(size > 0){
  12.             TreeNode cur = queue.poll();
  13.             size--;
  14.             row.add(cur.val);
  15.             if(cur.left != null){
  16.                 queue.offer(cur.left);
  17.             }
  18.             if(cur.right != null){
  19.                 queue.offer(cur.right);
  20.             }
  21.         }
  22.         ret.add(row);
  23.     }
  24.     return ret;
  25. }

7.找到俩个二叉树的公共祖先

  1. //找俩个节点的公共祖先,方法1
  2. public TreeNode lowestAncestor(TreeNode root,TreeNode p,TreeNode q){
  3.     if(root == null) return null;
  4.     if(root == p || root == q) return root;
  5.     
  6.     TreeNode retleft = lowestAncestor(root.left,p,q);
  7.     TreeNode retright = lowestAncestor(root.right,p,q);
  8.     
  9.     if(retleft != null && retright != null){
  10.         return root;
  11.     } else if (retleft != null) {
  12.         return retleft;
  13.     }else{
  14.         return retright;
  15.     }
  16. }
  17. //找俩个节点的公共祖先,方法2:找到根节点到指定节点之间的所有节点，存到stack中
  18. private boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack){
  19.     if(root == null || node == null) return false;
  20.     stack.push(root);
  21.     if(root == node) return true;
  22.     boolean ret1 = getPath(root.left,node,stack);
  23.     if(ret1 == true) return true;
  24.     boolean ret2 = getPath(root.right,node,stack);
  25.     if(ret2 == true) return true;
  26.     
  27.     stack.pop();
  28.     return false;
  29. }
  30. public TreeNode lowestAncestor2(TreeNode root,TreeNode p,TreeNode q){
  31.     if(root == null || p == null || q == null) return null;
  32.     Stack<TreeNode> stack1 = new Stack<>();
  33.     getPath(root,p,stack1);
  34.     
  35.     Stack<TreeNode> stack2 = new Stack<>();
  36.     getPath(root,q,stack2);
  37.     
  38.     int size1 = stack1.size();
  39.     int size2 = stack2.size();
  40.     
  41.     if(size1 > size2){
  42.         int tmp = size1 - size2;
  43.         while(tmp != 0){
  44.             stack1.pop();
  45.             tmp--;
  46.         }
  47.     }else{
  48.         int tmp = size2 - size1;
  49.         while(tmp != 0){
  50.             stack2.pop();
  51.             tmp--;
  52.     }
  53.     while(! stack1.empty() && !stack2.empty()){
  54.         if(stack1.peek() == stack2.peek()){
  55.             return stack1.peek();
  56.         }else{
  57.             stack1.pop();
  58.             stack2.pop();
  59.         }
  60.     }
  61.     return null;
  62. }

8.将二叉搜索树转换成排序双向链表

  1. //二叉搜索树转换成排序双向链表
  2. public TreeNode prev = null;
  3. private void ConvertChild(TreeNode root){
  4.     if(root == null) return ;
  5.     ConvertChild(root.left);
  6.     root.left = prev;
  7.     if(prev != null){
  8.         prev.right = root;
  9.     }
  10.     prev = root;
  11.     ConvertChild(root.right);
  12. }
  13. public TreeNode Convert(TreeNode pRootOfTree){
  14.     if(pRootOfTree == null) return null;
  15.     ConvertChild(pRootOfTree);
  16.     TreeNode head = pRootOfTree;
  17.     while(head.left != null){
  18.         head = head.left;
  19.     }
  20.     return head;
  21. }

9.根据前序和后序遍历构造二叉树

  1. //根据前序和中序遍历构造二叉树
  2. public int preindex = 0;
  3. private TreeNode buildTreeChild(int[] preorder,int[] inorder,int inbegin,int inend){
  4.     //没有了左树或没有右树
  5.     if(inbegin > inend) return null;
  6.     TreeNode root = new TreeNode(preorder[preindex]);
  7.     
  8.     //找到当前根节点在中序遍历中的位置
  9.     int rootIndex = findInorderIndex(inorder,preorder[preindex],inbegin,inend);
  10.     preindex++;
  11.     root.left = buildTreeChild(preorder,inorder,inbegin,rootIndex-1);
  12.     root.right = buildTreeChild(preorder,inorder,rootIndex+1,inend);
  13.     return root;
  14. }
  15. private int findInorderIndex(int[] inorder,int val,int inbegin,int inend){
  16.     for (int i = inbegin; i <= inend; i++) {
  17.         if (inorder[i] == val){
  18.             return i;
  19.         }
  20.     }
  21.     return -1;
  22. }
  23. public TreeNode buildTree(int[] preorder,int[] inorder){
  24.     return buildTreeChild(preorder,inorder,0,inorder.length-1);
  25. }

10.根据中序和后序遍历构造二叉树

  1. //根据中序和后序遍历构造二叉树
  2. public int postindex = 0;
  3. private TreeNode buildTreeChild(int[] postorder,int[] inorder,int inbegin,int inend){
  4.     //没有了左树或没有右树
  5.     if(inbegin > inend) return null;
  6.     TreeNode root = new TreeNode(postorder[postindex]);
  7.  
  8.     //找到当前根节点在中序遍历中的位置
  9.     int rootIndex = findInorderIndex(inorder,postorder[postindex],inbegin,inend);
  10.     postindex--;
  11.     root.right = buildTreeChild(postorder,inorder,rootIndex+1,inend);
  12.     root.left = buildTreeChild(postorder,inorder,inbegin,rootIndex-1);
  13.     return root;
  14. }
  15. private int findInorderIndex(int[] inorder,int val,int inbegin,int inend){
  16.     for (int i = inbegin; i <= inend; i++) {
  17.         if (inorder[i] == val){
  18.             return i;
  19.         }
  20.     }
  21.     return -1;
  22. }
  23. public TreeNode buildTree(int[] postorder,int[] inorder){
  24.     postindex = postorder.length-1;
  25.     return buildTreeChild(postorder,inorder,0,inorder.length-1);
  26. }

11.二叉树创建字符串

  1. //二叉树创建字符串
  2. public String tree2str(TreeNode root) {
  3.     StringBuilder sb = new StringBuilder();
  4.     tree2strChild(root,sb);
  5.     return sb.toString();
  6. }
  7.  
  8. private void tree2strChild(TreeNode t,StringBuilder sb) {
  9.     if(t == null) return ;
  10.     sb.append(t.val);
  11.  
  12.     if(t.left != null) {
  13.         sb.append("(");
  14.         tree2strChild(t.left,sb);
  15.         sb.append(")");
  16.     }else {
  17.         if(t.right == null) {
  18.             return;
  19.         }else{
  20.             sb.append("()");
  21.         }
  22.     }
  23.  
  24.     if(t.right == null) {
  25.         return;
  26.     }else{
  27.         sb.append("(");
  28.         tree2strChild(t.right,sb);
  29.         sb.append(")");
  30.     }
  31. }

12.非递归实现前序遍历

  1. //非递归实现前序遍历
  2. public  void preorderTraversalNor(TreeNode root) {
  3.     Stack<TreeNode> stack = new Stack<>();
  4.     TreeNode cur = root;
  5.  
  6.     while (cur != null || !stack.empty()) {
  7.         while (cur != null) {
  8.             stack.push(cur);
  9.             System.out.print(cur.val + " ");
  10.             cur = cur.left;
  11.         }
  12.  
  13.         TreeNode top = stack.pop();
  14.         cur = top.right;
  15.     }
  16. }

13.非递归实现中序遍历

  1. //非递归实现中序遍历
  2. public void inorderTraversal(TreeNode root) {
  3.     Stack<TreeNode> stack = new Stack<>();
  4.     TreeNode cur = root;
  5.     while (cur != null || !stack.empty()) {
  6.         while (cur != null) {
  7.             stack.push(cur);
  8.             cur = cur.left;
  9.         }
  10.         TreeNode top = stack.pop();
  11.         System.out.print(top.val + " ");
  12.         cur = top.right;
  13.     }
  14. }
  15.

14.非递归实现后序遍历

  1. //非递归实现后序遍历
  2. public void postorderTraversal(TreeNode root) {
  3.     Stack<TreeNode> stack = new Stack<>();
  4.     TreeNode prev = null;
  5.     TreeNode cur = root;
  6.     while (cur != null || !stack.empty()) {
  7.         while (cur != null) {
  8.             stack.push(cur);
  9.             cur = cur.left;
  10.         }
  11.         TreeNode top = stack.peek();
  12.         //top.right 如果已经被访问了 也要弹出top所指向的节点
  13.         if (top.right == null || top.right == prev) {
  14.             stack.pop();
  15.             System.out.print(top.val + " ");
  16.             prev = top;
  17.         } else {
  18.             cur = top.right;
  19.         }
  20.     }
  21. }

如果对您有帮助的话，

不要忘记点赞+关注哦，蟹蟹

如果对您有帮助的话，

不要忘记点赞+关注哦，蟹蟹

如果对您有帮助的话，

不要忘记点赞+关注哦，蟹蟹

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

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

  

闽ICP备14008679号