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

树 和 二叉树

作者：知新_RL | 2024-04-17 11:27:23

赞

踩

树 和 二叉树

目录

一、树

1、初识树

2、树的一些概念

3、树的表示形式

二、二叉树

1、初识二叉树

2、两种特殊的二叉树

3、二叉树的性质 

4、二叉树的遍历

5、实现一棵二叉树 

6、二叉树题目（没代码的后面会给补上）

一、树

1、初识树

（1）根节点没有前驱。

（2）子树的根节点只有一个前驱，可以有0个或多个后继。

（3）每个子树都是不相交的，子树之间不能有交集。

（4）N个结点有N-1条边

2、树的一些概念

1、结点的度：这个结点有几个子树，度就为几

2、树的度：所有结点度的最大值就是树的度

3、根结点：没有前驱的结点

4、叶子结点或终端结点：没有后继的结点（没有子树），即度为0的结点

5、分支结点或非终端结点：有后继的结点（有子树），即度不为0的结点

6、双亲结点或父结点：结点的前驱就是该结点的父结点

7、孩子结点或子结点：结点的后继就是该结点的子结点

8、兄弟结点：具有相同父结点的结点互为兄弟结点

9、堂兄弟结点：父结点在同一层的结点互为堂兄弟结点

10、结点的祖先：从根结点到该结点一路上经过的所有结点都是该结点的祖先，如：根结点是除自身外所有结点的祖先

11、子孙：该结点后面的所有结点都是该结点的子孙，如：除根结点外所有结点都是根结点的子孙

12、结点的层次：根为第1层，以此类推

13、深度：该结点的层次就是深度

14、树的高度：树中结点的最大层次就是树的高度

15、森林：由m（m>=0）棵互不相交的树组成的集合称为森林，空树也叫森林

3、树的表示形式

树可以有：双亲表示法，孩子表示法，孩子双亲表示法，孩子兄弟表示法等等

二、二叉树

1、初识二叉树

（1）二叉树是树

（2）二叉树的每个根结点都只有两棵子树，分别为左子树和右子树

（3）二叉树也可以是空树

（4）二叉树的度 <=2，所以二叉树的结点个数 = 度为0的结点个数+度为1的结点个数+度为2的结点个数

2、两种特殊的二叉树

（1）满二叉树

除叶子结点外，结点的度都为2，结点总数为：(2^k)-1，k为树的高度

（2）完全二叉树

从上到下，从左到右，中间不少结点。

满二叉树是特殊的完全二叉树。

完全二叉树中，度为1的结点个数 要么为0，要么为1 —— 结点总数是偶数时，度为1的结点个数为 1，结点总数是奇数时，度为1的结点个数为 0

3、二叉树的性质 

1、二叉树的第 k 层，最多有 2^(k-1) 个结点（空树除外）

2、深度为 k 的二叉树，最多有(2^k)-1个结点

3、任意一棵二叉树，叶子结点的个数 比 度为2的结点的个数 多 1

4、n个结点的完全二叉树，深度k为：(2^k) -1= n，k为 log以2为底n+1的对数，向上取整

5、完全二叉树，

若父结点下标为 i，则 左孩子下标为：2*i+1，右孩子下标为：2*i+2

若子结点下标为 i，则父结点下标为：​​​​​​​（i-1）/2

题目：

1. 某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（B、 200 ）199+1

2.在具有 2n 个结点的完全二叉树中，叶子结点个数为（A、n）2n = n0+1+n0-1

3.一个具有767个节点的完全二叉树，其叶子节点个数为（B、384）767 = n0+0+n0-1

4、二叉树的遍历

前序遍历：根，左子树，右子树

中序遍历：左子树，根，右子树

后序遍历：左子树，右子树，根

层序遍历：从上到下，从左到右

如：写出下面这棵二叉树的前序遍历，中序遍历，后序遍历，层序遍历的结果

前序遍历：A B D E H C F G

中序遍历：D B E H A F C G

后序遍历：D H E B F G C A

层序遍历：A B C D E F G H

题目：

1、设一课二叉树的中序遍历序列：badce，后序遍历序列：bdeca，则二叉树前序遍历序列为(D)

A: adbce B: decab C: debac D: abcde

后序遍历，从后往前，每一个结点都是根结点。拿着根结点，去中序遍历里看，根结点的左边属于左子树的结点，根结点的右边属于右子树的结点。

如，后序遍历从后往前第一个结点就是整棵树的根结点 a，然后看中序遍历，则，b 属于左子树的结点，dce 属于右子树的结点。然后再看后序遍历从后往前第二个结点，以此类推。

由此题引出两个问题，

问题一：如果只给一个遍历，能否创建一棵二叉树？

不能。因为有可能存在两棵不同的树，某一个遍历是一样的。

问题二：如果只给前序遍历和后序遍历，能否创建一棵二叉树？

不能。前序遍历和后序遍历都是只能确定根的位置，但不能确定左子树或右子树。

5、实现一棵二叉树 

二叉树的存储结构（物理结构）有：顺序存储和链式存储

这里我们使用孩子表示法来实现一个链式存储结构的二叉树。

1、前序遍历 2、中序遍历 3、后序遍历
4、获取树中结点的个数 5、获取叶子结点的个数 6、获取第 k层 结点的个数
7、获取二叉树的高度
8、获取第k层的所有结点：有点 带返回值的前序遍历 和 获取第 k层 结点的个数 的结合版
9、找到值为value的元素
10、层序遍历：和层序遍历相关的想到用 队列，用队列会比较方便
11、判断这棵树是不是完全二叉树：用 队列
  1. public class MyBinaryTree {
  2.     static class TreeNode{
  3.         public char val;
  4.         public TreeNode leftTree;//存储左子树的引用
  5.         public TreeNode rightTree;//存储右子树的引用
  6.         public TreeNode(char val){
  7.             this.val = val;
  8.         }
  9.     }
  10.     //创建一棵树
  11.     public TreeNode createTree(){
  12.         TreeNode A = new TreeNode('A');
  13.         TreeNode B = new TreeNode('B');
  14.         TreeNode C = new TreeNode('C');
  15.         TreeNode D = new TreeNode('D');
  16.         TreeNode E = new TreeNode('E');
  17.         TreeNode F = new TreeNode('F');
  18.         TreeNode G = new TreeNode('G');
  19.         TreeNode H = new TreeNode('H');
  20.         A.leftTree = B;
  21.         A.rightTree = C;
  22.         B.leftTree = D;
  23.         B.rightTree = E;
  24.         C.leftTree = F;
  25.         C.rightTree = G;
  26.         E.rightTree = H;
  27.         return A;
  28.     }
  29.     //前序遍历
  30.     public void preOrder(TreeNode root){
  31.         if(root == null){
  32.             return;
  33.         }
  34.         System.out.print(root.val+" ");
  35.         preOrder(root.leftTree);
  36.         preOrder(root.rightTree);
  37.     }
  38.     //带返回值
  39.     public List<Character> preorderTraversal(TreeNode root) {
  40.         //子问题思路：先放根，然后放左子树，然后放右子树
  41.         List<Character> list = new ArrayList<>();
  42.         //递归的终止条件
  43.         if(root == null){
  44.             return list;
  45.         }
  46.         list.add(root.val);
  47.         list.addAll(preorderTraversal(root.leftTree));
  48.         list.addAll(preorderTraversal(root.rightTree));
  49.         return list;
  50.     }
  51.     //中序遍历
  52.     public void inOrder(TreeNode root){
  53.         if(root == null){
  54.             return;
  55.         }
  56.         inOrder(root.leftTree);
  57.         System.out.print(root.val+" ");
  58.         inOrder(root.rightTree);
  59.     }
  60.     //后序遍历
  61.     public void postOrder(TreeNode root){
  62.         if(root == null){
  63.             return;
  64.         }
  65.         postOrder(root.leftTree);
  66.         postOrder(root.rightTree);
  67.         System.out.print(root.val+" ");
  68.     }
  69.     //获取树中结点的个数
  70.     public int size(TreeNode root){
  71.         //左子树结点的个数+右子树结点的个数+1
  72.         //递归的终止条件
  73.         if(root == null){
  74.             return 0;
  75.         }
  76.         return size(root.leftTree)+size(root.rightTree)+1;
  77.     }
  78.     //获取叶子结点的个数
  79.     public int getLeafNodeCount(TreeNode root){
  80.         //左子树叶子结点的个数+右子树叶子结点的个数
  81.         if(root == null){
  82.             return 0;
  83.         }
  84.         //满足下面条件的就是叶子结点,递归的终止条件
  85.         if(root.leftTree == null && root.rightTree == null){
  86.             return 1;
  87.         }
  88.         return getLeafNodeCount(root.leftTree) + getLeafNodeCount(root.rightTree);
  89.     }
  90.     //获取第 k层 结点的个数
  91.     public int getKLevelNodeCount(TreeNode root,int k){
  92.         //第k层结点的个数 = 左子树第k-1层结点的个数+右子树第k-1层结点的个数
  93.         if(k <= 0){
  94.             throw new KWrongFulException("k不合法异常");
  95.         }
  96.         //如果k大于树的高度，k还没减到0，root先变成null，返回0
  97.         //下面两个都算循环的终止条件
  98.         if(root == null){
  99.             return 0;
  100.         }
  101.         if(k == 1){
  102.             return 1;
  103.         }
  104.         return getKLevelNodeCount(root.leftTree,k-1)
  105.                 +getKLevelNodeCount(root.rightTree,k-1);
  106.     }
  107.     //获取二叉树的高度
  108.     public int getHeight(TreeNode root){
  109.         //左子树的高度，右子树的高度的最大值 +1
  110.         if(root == null){
  111.             return 0;
  112.         }
  113.         int leftHeight = getHeight(root.leftTree);
  114.         int rightHeight = getHeight(root.rightTree);
  115.         return leftHeight > rightHeight ? leftHeight+1 : rightHeight+1;
  116.     }
  117.     //获取第 k 层的所有结点
  118.     //有点像 带返回值的前序遍历 和 获取第 k层 结点的个数 的结合
  119.     public List<Character> KLevel(TreeNode root,int k){
  120.         List<Character> list = new LinkedList<>();
  121.         if(root == null){
  122.             return list;
  123.         }
  124.         //把 第 k 层的每一个结点都 add 进 list，返回给父结点
  125.         if(k == 1){
  126.             list.add(root.val);
  127.             return list;
  128.         }
  129.         //父结点接收到两个子结点返回的 list，add到自己的list里
  130.         list.addAll(KLevel(root.leftTree,k-1));
  131.         list.addAll(KLevel(root.rightTree,k-1));
  132.         //然后返回给他的父结点，于是层层递进，最后根结点的list里 放的就是 第k层 的所有结点
  133.         return list;
  134.     }
  135.     //找到值为value的元素
  136.     public TreeNode find(TreeNode root,char val){
  137.         //先找根，然后找左子树，然后找右子树，找到就返回，找不到返回null
  138.         //下面两个都是递归的终止条件
  139.         if(root == null){
  140.             return null;
  141.         }
  142.         if(root.val == val){
  143.             return root;
  144.         }
  145.         TreeNode ret1 = find(root.leftTree,val);
  146.         //如果 ret1 里面不是空，说明找到了
  147.         //如果 ret1 里面是空，说明没找到
  148.         if (ret1 != null){
  149.             return ret1;
  150.         }
  151.         TreeNode ret2 = find(root.rightTree,val);
  152.         if (ret2 != null){
  153.             return ret2;
  154.         }
  155.         return null;
  156.     }
  157.     //层序遍历：用到队列，先进先出
  158.     //层序遍历不用递归比较方便，本来就是按顺序（从上到下，从左到右）输出的呀，
  159.     // 不像前序中序和后序遍历，必须得递归
  160.     public void levelOrder(TreeNode root){
  161.         Queue<TreeNode> queue = new LinkedList<>();
  162.         if(root == null){
  163.             return;
  164.         }
  165.         queue.offer(root);
  166.         while(!queue.isEmpty()){
  167.             TreeNode ret = queue.poll();
  168.             System.out.print(ret+" ");
  169.             if(ret.leftTree != null){
  170.                 queue.offer(ret.leftTree);
  171.             }
  172.             if(ret.leftTree != null){
  173.                 queue.offer(ret.rightTree);
  174.             }
  175.         }
  176.     }
  177.     //有返回值的层序遍历：用到队列比较方便
  178.     //难点在如何确定每一层，这里我们用到了队列中的size
  179.     //每一轮都要定义一个size
  180.     public List<List<Character>> levelOrderTraversal(TreeNode root){
  181.         List<List<Character>> tmp = new ArrayList<>();
  182.         Queue<TreeNode> queue = new LinkedList<>();
  183.         if(root == null){
  184.             return tmp;
  185.         }
  186.         queue.offer(root);
  187.         while(!queue.isEmpty()){
  188.             int size = queue.size();
  189.             List<Character> list = new ArrayList<>();
  190.             while(size > 0) {
  191.                 TreeNode ret = queue.poll();
  192.                 size--;
  193.                 list.add(ret.val);
  194.                 if (ret.leftTree != null) {
  195.                     queue.offer(ret.leftTree);
  196.                 }
  197.                 if (ret.rightTree != null) {
  198.                     queue.offer(ret.rightTree);
  199.                 }
  200.             }
  201.             tmp.add(list);
  202.         }
  203.         return tmp;
  204.     }
  205.     //判断这棵树是不是完全二叉树：用队列
  206.     public boolean isCompleteTree(TreeNode root){
  207.         Queue<TreeNode> queue = new LinkedList<>();
  208.         if(root == null){
  209.             return true;
  210.         }
  211.         queue.offer(root);
  212.         while(!queue.isEmpty()){
  213.             TreeNode ret = queue.peek();
  214.             if(ret == null){
  215.                 break;
  216.             }
  217.             queue.poll();
  218.             queue.offer(ret.leftTree);
  219.             queue.offer(ret.rightTree);
  220.         }
  221.         //走到这，队列里要么都是null，要么除了null还有结点，后者说明不是完全二叉树
  222.         while(!queue.isEmpty()){
  223.             TreeNode ret = queue.poll();
  224.             if(ret != null){
  225.                 return false;
  226.             }
  227.         }
  228.         return true;
  229.     }
  230. }

6、二叉树题目（没代码的后面会给补上）

1、判断两棵树相不相等
2、判断其中一棵树是不是另一棵树的子树
3、翻转二叉树
4、判断是不是平衡二叉树
5、判断两棵二叉树是不是镜像对称
6、判断是不是轴对称二叉树
7、二叉树的层序遍历
8、二叉树的构建和遍历
9、给定一个二叉树, 找到该树中两个指定节点的最近公共祖先
10、二叉搜索树转换成排序双向链表
11、二叉树前序非递归遍历实现
12、二叉树中序非递归遍历实现
13、二叉树后序非递归遍历实现
14、根据一棵树的前序遍历与中序遍历构造二叉树
15、根据一棵树的中序遍历与后序遍历构造二叉树
16、二叉树创建字符串

（1）判断两棵树是否相同 链接

  1. //时间复杂度：O(min(m,n))，其中 m和n 分别是两个二叉树的结点数
  2. public boolean isSameTree(TreeNode p, TreeNode q) {
  3.         //先判断根一样不，再判断左子树一样不，再判断右子树一样不，只有全一样(结构和值都一样)，才返回true
  4.         //如果都是空树
  5.         if(p == null && q == null){
  6.             return true;
  7.         }
  8.         //如果一个是空树，一个不是
  9.         if((p == null && q != null) || (p != null && q == null)){
  10.             return false;
  11.         }
  12.         //走到这，则两个都不是空树
  13.         //值不相等
  14.         if(p.val != q.val){
  15.             return false;
  16.         }
  17.         //走到这，既不是空树，根的值也相等
  18.         return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
  19. }

（2）判断其中一棵树是不是另一棵树的子树 链接 

  1.  
  2.     /**
  3.      * 2、判断其中一棵树是不是另一棵树的子树
  4.      * 时间复杂度：O(m*n)，其中 m和n 分别是两个二叉树的结点数
  5.      */
  6.     public boolean isSubtree(TreeNode root, TreeNode subRoot) {
  7.         //题目中已经给出了：两棵树都不是空树
  8.         //如果一直没有匹配，root就会一直root.left，root会为空
  9.         if(root == null || subRoot == null){
  10.             return false;
  11.         }
  12.         //先判断subRoot是否和root相等，
  13.         if(isSameTree(root,subRoot)) return true;
  14.         //再判断subRoot是否是root的左子树的子树
  15.         if(isSubtree(root.left,subRoot)) return true;
  16.         //再判断subroot是否是root的右子树的子树
  17.         if(isSubtree(root.right,subRoot)) return true;
  18.         return false;
  19.     }
  20.    public boolean isSameTree(TreeNode p, TreeNode q) {
  21.         //先判断根一样不，再判断左子树一样不，再判断右子树一样不，只有全一样(结构和值都一样)，才返回true
  22.         //如果都是空树
  23.         if(p == null && q == null){
  24.             return true;
  25.         }
  26.         //如果一个是空树，一个不是
  27.         if((p == null && q != null) || (p != null && q == null)){
  28.             return false;
  29.         }
  30.         //走到这，则两个都不是空树
  31.         //值不相等
  32.         if(p.val != q.val){
  33.             return false;
  34.         }
  35.         //走到这，既不是空树，根的值也相等
  36.         return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
  37.     }

（3）翻转二叉树 链接

  1. public TreeNode invertTree(TreeNode root) {
  2.         //先翻转根结点的左子树和右子树，再翻转左子树的左子树和右子树，再翻转右子树的左子树和右子树
  3.         if(root == null){
  4.             return null;
  5.         }
  6.         TreeNode tmp = root.left;
  7.         root.left = root.right;
  8.         root.right = tmp;
  9.         invertTree(root.left);
  10.         invertTree(root.right);
  11.         return root;
  12. }

（4）判断是不是平衡二叉树 链接

  1. //判断是不是平衡二叉树，时间复杂度O(n)
  2.     public boolean isBalanced(TreeNode root) {
  3.         //平衡二叉树：每棵子树的高度差都要 <=1
  4.  
  5.         if(root == null){
  6.             return true;
  7.         }
  8.         int ret = height(root);
  9.         if(ret == -1){
  10.             return false;
  11.         }
  12.         return true;
  13.     }
  14.     //求二叉树的高度，时间复杂度是O(n)
  15.     //求根结点高度的时候，其实已经求了所有结点的高度，如果发现左树右树高度差大于1，说明已经不平衡了，就返回-1
  16.     //否则就返回左树右树高度最大值+1
  17.     //所以，我们需要在每次获得左树和右树高度的时候，都接收判断一下，如果发现接收到的是-1，说明已经出现了不平衡
  18.     //如果一直没有接收到-1，说明这个二叉树的每棵子树都是平衡的，所以这棵二叉树是高度平衡的二叉树。
  19.     //求二叉树的高度
  20.     public int height(TreeNode root){
  21.         if(root == null){
  22.             return 0;
  23.         }
  24.         //求左子树的高度
  25.         int leftH = height(root.left);
  26.         if(leftH == -1){
  27.             return -1;
  28.         }
  29.         //求右子树的高度
  30.         int rightH = height(root.right);
  31.         if(rightH == -1){
  32.             return -1;
  33.         }
  34.         //如果左右子树的高度差 <= 1，返回左右子树高度的最大值+1
  35.         //如果左右子树的高度差 > 1，返回-1，说明已经出现不平衡了
  36.         if(Math.abs(leftH - rightH) <= 1){
  37.             return Math.max(leftH,rightH) + 1;
  38.         }else{
  39.             return -1;
  40.         }
  41.     }

（5）判断两棵树是不是镜像对称

  1. public boolean isMirrorSymmetry(TreeNode leftTree,TreeNode rightTree){
  2.         //如果两个都是空树
  3.         if(leftTree == null && rightTree == null){
  4.             return true;
  5.         }
  6.         //如果一个是空树一个不是
  7.         if((leftTree == null && rightTree != null) || (leftTree != null && rightTree == null)){
  8.             return false;
  9.         }
  10.         //到这，两个都不是空树
  11.         if(leftTree.val != rightTree.val){
  12.             return false;
  13.         }
  14.         //到这，两个都不是空树，且根的值相同
  15.         return isMirrorSymmetry(leftTree.left,rightTree.right) &&
  16.                 isMirrorSymmetry(leftTree.right,rightTree.left);
  17. }

（6）判断是不是轴对称二叉树 链接

  1. public boolean isSymmetric(TreeNode root) {
  2.         
  3.         if(root == null){
  4.             return true;
  5.         }
  6.         //从第二层开始，比较左子树和右子树是否是镜像的
  7.         return isMirrorSymmetry(root.left,root.right);
  8.     }
  9.     //先比较根是否是镜像的，再比较子树是否是镜像的
  10.      public boolean isMirrorSymmetry(TreeNode leftTree,TreeNode rightTree){
  11.         //如果两个都是空树
  12.         if(leftTree == null && rightTree == null){
  13.             return true;
  14.         }
  15.         //如果一个是空树一个不是
  16.         if((leftTree == null && rightTree != null) || (leftTree != null && rightTree == null)){
  17.             return false;
  18.         }
  19.         //到这，两个都不是空树
  20.         if(leftTree.val != rightTree.val){
  21.             return false;
  22.         }
  23.         //到这，两个都不是空树，且根的值相同
  24.         return isMirrorSymmetry(leftTree.left,rightTree.right) &&
  25.                 isMirrorSymmetry(leftTree.right,rightTree.left);
  26.     }

（7）二叉树的层序遍历 链接

  1. //有返回值的层序遍历：用到队列比较方便
  2. //难点在如何确定每一层，这里我们用到了队列中的size
  3. //每一轮都要定义一个size
  4.  public List<List<Integer>> levelOrder(TreeNode root) {
  5.        List<List<Integer>> tmp = new ArrayList<>();
  6.         Queue<TreeNode> queue = new LinkedList<>();
  7.         if(root == null){
  8.             return tmp;
  9.         }
  10.         queue.offer(root);
  11.         while(!queue.isEmpty()){
  12.             int size = queue.size();
  13.             List<Integer> list = new ArrayList<>();
  14.             while(size > 0) {
  15.                 TreeNode ret = queue.poll();
  16.                 size--;
  17.                 list.add(ret.val);
  18.                 if (ret.left != null) {
  19.                     queue.offer(ret.left);
  20.                 }
  21.                 if (ret.right != null) {
  22.                     queue.offer(ret.right);
  23.                 }
  24.             }
  25.             tmp.add(list);
  26.         }
  27.         return tmp;
  28. }

（8）二叉树的构建和遍历 链接

  1. public class Main {
  2.     static class TreeNode{
  3.         public char val;
  4.         public TreeNode leftTree;//存储左子树的引用
  5.         public TreeNode rightTree;//存储右子树的引用
  6.         public TreeNode(char val){
  7.             this.val = val;
  8.         }
  9.     }
  10.     public static void main(String[] args) {
  11.         Scanner scanner = new Scanner(System.in);
  12.         while (scanner.hasNextLine()) { 
  13.             String str = scanner.nextLine();//str里存的就是读入的字符串
  14.  
  15.            //首先遍历字符串，拿到字符串中的每个元素，
  16.            //并创建结点，通过前序遍历构造一棵二叉树
  17.            TreeNode root = createTree(str);
  18.            //然后再中序遍历输出
  19.            inOrder(root);
  20.         }
  21.     }
  22.     //通过前序遍历构造二叉树
  23.     public static int i = 0;
  24.     public static TreeNode createTree(String str){
  25.         TreeNode root = null;
  26.         //通过i拿到字符串中的每个字符
  27.         char ch = str.charAt(i);
  28.         i++;
  29.         if(ch == '#'){
  30.             return null;
  31.         }
  32.         //把拿到的元素创建成结点
  33.         root = new TreeNode(ch);
  34.         root.leftTree = createTree(str);
  35.         root.rightTree = createTree(str);
  36.         return root;   
  37.     }
  38.     //中序遍历输出
  39.     public static void inOrder(TreeNode root){
  40.         if(root == null){
  41.             return;
  42.         }
  43.         inOrder(root.leftTree);
  44.         System.out.print(root.val+" ");
  45.         inOrder(root.rightTree);
  46.     }
  47. }

（9）给定一个二叉树, 找到该树中两个指定节点的最近公共祖先  链接

  1.  public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
  2.         if(root == null){
  3.             return null;
  4.         }
  5.         // p 和 q 其中有一个是root
  6.         if(p == root || q == root){
  7.             return root;
  8.         }
  9.         // p 和 q 分别在 root 的两侧
  10.         // p 和 q 都在 root 的左侧 或 root 的右侧
  11.         TreeNode ret1 = lowestCommonAncestor(root.left,p,q);
  12.         TreeNode ret2 = lowestCommonAncestor(root.right,p,q);
  13.         if(ret1 != null && ret2 != null){
  14.             return root;
  15.         }else if(ret1 != null){
  16.             return ret1;
  17.         }else if(ret2 != null){
  18.             return ret2;
  19.         }else{
  20.             return null;
  21.         }
  22. }

（10）二叉搜索树转换成排序双向链表 链接

  1. public TreeNode convert(TreeNode pRootOfTree) {
  2.         //二叉搜索树：根左边的比根小，根右边的比根大
  3.         //中序遍历二叉搜索树是有序的，是从小到大的
  4.         //所以，转换成排序的双向链表，采用中序遍历的方法
  5.         if(pRootOfTree == null){
  6.             return null;
  7.         }
  8.         convertChild(pRootOfTree);
  9.         TreeNode head = pRootOfTree;
  10.         //链表的头就是二叉搜素树最左边的那个结点
  11.         while(head.left != null){
  12.             head = head.left;
  13.         }
  14.         return head;
  15.     }
  16.     public TreeNode prev = null;
  17.     public void convertChild(TreeNode pRoot){
  18.         if(pRoot == null){
  19.             return;
  20.         }
  21.         convertChild(pRoot.left);
  22.  
  23.         if(prev != null){
  24.             prev.right = pRoot;
  25.         }
  26.         pRoot.left = prev;
  27.         prev = pRoot;
  28.         convertChild(pRoot.right);
  29.  }

（11）二叉树前序非递归遍历实现 链接

  1. public TreeNode cur = null;
  2.     public List<Integer> preorderTraversal(TreeNode root) {
  3.         Stack<TreeNode> stack = new Stack<>();
  4.         List<Integer> list = new ArrayList<>();
  5.         //用到栈
  6.         //前序遍历：根，左，右。往左走，一直入栈，只有这个节点没用了，才能出栈。
  7.         if(root == null){
  8.             return list;
  9.         }
  10.         cur = root;
  11.         while(cur != null || !stack.empty()){
  12.             while(cur != null){
  13.                 stack.push(cur);
  14.                 list.add(cur.val);
  15.                 cur = cur.left;
  16.             }
  17.             //cur 等于空，说明cur的左走完了，此时栈顶元素就是cur
  18.             //根和左走完了，此时才能弹出栈顶元素（因为直到这时栈顶元素才没用了）
  19.             cur = stack.pop();
  20.             cur = cur.right;
  21.         }
  22.         return list;
  23.  }

（12）二叉树中序非递归遍历实现 链接

（13）二叉树后序非递归遍历实现 链接

（14）根据一棵树的前序遍历与中序遍历构造二叉树 链接

（15）根据一棵树的中序遍历与后序遍历构造二叉树 链接

（16）二叉树创建字符串 链接

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

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

  

闽ICP备14008679号