深圳幻海软件技术有限公司 欢迎您！
更多

二叉树【数据结构】【超详细，一学就会】

2023-06-26

null left root
目录📖1.什么是二叉树？🌴2.满二叉树和完全二叉树 ⛳2.二叉树的性质🔥3.二叉树的创建与遍历3.1创建二叉树3.2前中后序遍历——递归和非递归🏹4.二叉树的实现1️⃣获取树中节点的个数2️⃣获取叶子节点的个数3️⃣获取第K层节点的个数4️⃣获取二叉树的高度5️⃣检测值为value

目录

📖1.什么是二叉树？

🌴2.满二叉树和完全二叉树

 ⛳2.二叉树的性质

🔥3.二叉树的创建与遍历

3.1 创建二叉树

3.2 前中后序遍历——递归和非递归

🏹4.二叉树的实现

1️⃣获取树中节点的个数

2️⃣获取叶子节点的个数

3️⃣获取第K层节点的个数

4️⃣获取二叉树的高度

5️⃣检测值为value的元素是否存在

6️⃣判断两棵树是否相同【leetcod】

7️⃣另一棵树的子树【leetcod】

8️⃣翻转二叉树【leetcod】

🔟平衡二叉树【leetcod】

⏸二叉树的层序遍历

二叉树的分层遍历【leetcod】

📜5.二叉树的练习

1️⃣二叉树遍历【牛客网】

2️⃣二叉树的最近公共祖先【leetcod】

3️⃣从前序与中序遍历序列构造二叉树【leetcod】

4️⃣从中序与后序遍历序列构造二叉树【leetcod】

5️⃣根据二叉树创建字符串【leetcod】

6️⃣判断一棵树是不是完全二叉树

 

📖1.什么是二叉树？

结点的度：一个结点含有子树的个数称为该结点的度； 如上图：A的度为2

树的度：一棵树中，所有结点度的最大值称为树的度； 如上图：树的度为2

叶子结点或终端结点：度为0的结点称为叶结点； 如上图：H、I、J、K、G等节点为叶结点

双亲结点或父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点； 如上图：A是B的父结点

孩子结点或子结点：一个结点含有的子树的根结点称为该结点的子结点； 如上图：B是A的孩子结点

根结点：一棵树中，没有双亲结点的结点；如上图：A

结点的层次：从根开始定义起，根为第1层，根的子结点为第2层，以此类推

树的高度或深度：树中结点的最大层次； 如上图：树的高度为4

📑一棵二叉树是结点的一个有限集合，该集合：

1️⃣或者为空 2️⃣或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成。

✨对于二叉树来说：每一个节点的度不能大于2，并且二叉树是一个有序树

🌴2.满二叉树和完全二叉树

满二叉树: 一棵二叉树，如果每层的结点数都达到最大值，则这棵二叉树就是满二叉树。也就是说，如果一棵二叉树的层数为K，且结点总数是 2^k - 1，第k层节点数是 2^(k-1) ,则它就是满二叉树。如果一共有n个节点，那么k=log2（n+1）

完全二叉树（最小深度）: 完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从0至n-1的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。——从左往右不可以空结点

 ⛳2.二叉树的性质

1️⃣一颗 N 节点的树有 N - 1 条边

2️⃣若规定根结点的层数为1，则一棵非空二叉树的第i层上最多有 2^i - 1（i>0）个结点

3️⃣若规定只有根结点的二叉树的深度为1，则深度为K的二叉树的最大结点数是  2^k - 1 (k>=0)

4️⃣具有n个结点的完全二叉树的深度k为 log2（n+1） 上取整

5️⃣对任何一棵二叉树, 如果其叶结点个数为 n0, 度为2的非叶结点个数为 n2,则有n0＝n2＋1 （度为0的节点是度为2的节点多1个）

 6️⃣偶数个结点的完全二叉树：度为1的结点个数为1；奇数个结点的完全二叉树：度为1的结点个数为0；

7️⃣对于具有n个结点的完全二叉树，如果按照从上至下从左至右的顺序对所有节点从0开始编号，则对于序号为i的结点有：

若i>0， 双亲序号： (i-1)/2； i=0 ， i 为根结点编号，无双亲结点
若 2i+1<n ，左孩子序号： 2i+1 ，否则无左孩子
若 2i+2<n ，右孩子序号： 2i+2 ，否则无右孩子

已知父亲结点下标是i：

左孩子：2*i+1   右孩子：2*i+2

已知孩子结点下标是i：

父亲结点下标：（i-1)/2

🔥3.二叉树的创建与遍历

3.1 创建二叉树

✨对于一个二叉树，我们定义一个数据域、左孩子域、右孩子域、根结点。对于一个二叉树，如图所示，总会有一个左结点和右结点（可以为null）

  1.     //创建二叉树
  2.     public class TreeNode {
  3.         public char val;//数据域
  4.         public TreeNode left;//左孩子的引用
  5.         public TreeNode right;//右孩子的引用
  6.  
  7.         //构造函数
  8.         public TreeNode(char val) {
  9.             this.val = val;
  10.         }
  11.     }
  12.  
  13.     public TreeNode root;//二叉树的根结点
  14.  
  15.     public TreeNode createTree() {
  16.         TreeNode A = new TreeNode('A');
  17.         TreeNode B = new TreeNode('B');
  18.         TreeNode C = new TreeNode('C');
  19.         TreeNode D = new TreeNode('D');
  20.         TreeNode E = new TreeNode('E');
  21.         TreeNode F = new TreeNode('F');
  22.         TreeNode G = new TreeNode('G');
  23.         TreeNode H = new TreeNode('H');
  24.         A.left = B;
  25.         A.right = C;
  26.         B.left = D;
  27.         B.right = E;
  28.         C.left = F;
  29.         C.right = G;
  30.         E.right = H;
  31.         this.root = A;
  32.         return root;
  33.     }

3.2 前中后序遍历——递归和非递归

遍历：历(Traversal)是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题(比如：打印节点内容、节点内容加1)。

1️⃣前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点--->根的左子树--->根的右子树

❗注意：每棵树都有根、左、右结点。并且这里边每个结点都可以作为孩子结点的根结点

  1.     //前序遍历  递归
  2.     public void preOrder(TreeNode root) {
  3.         if(root == null) {
  4.             return;
  5.         }
  6.         System.out.println(root.val + " ");//先打印再递归
  7.         preOrder(root.left);
  8.         preOrder(root.right);
  9.     }

非递归实现二叉树的前序遍历：使用栈完成——定义一个cur = root，把根节点放入栈中，同时进行打印，把根左边放入栈中，再进行打印，继续往左边走放入栈中，再进行打印；再往左边走，如果为null，则从栈中弹出这个元素给top；如果这个元素右边为null，则再弹出一个元素给top，循环以上过程

  1.     /非递归：    
  2.     public void preOrderNor(TreeNode root) {
  3.         if(root == null) {
  4.             return;
  5.         }
  6.         TreeNode cur = root;
  7.         Deque<TreeNode> stack = new ArrayDeque<>();
  8.         while (cur != null || stack.isEmpty()) {
  9.             while (cur != null) {
  10.                 stack.push(cur);
  11.                 System.out.print(cur.val + " ");
  12.                 cur = cur.left;
  13.             }
  14.             TreeNode top = stack.pop();
  15.             cur = top.right;
  16.         }
  17.         System.out.println();
  18.     }

2️⃣中序遍历(Inorder Traversal)——根的左子树--->根节点--->根的右子树。

 

  1.     //中序遍历
  2.     public void inOrder(TreeNode root) {
  3.         if(root == null) {
  4.             return;
  5.         }
  6.         inOrder(root.left);
  7.         System.out.println(root.val + " ");
  8.         inOrder(root.right);
  9.     }
  1.     //中序遍历非递归
  2.     public void inOrderNor(TreeNode root) {
  3.         if(root == null) {
  4.             return;
  5.         }
  6.         TreeNode cur = root;
  7.         Deque<TreeNode> stack = new ArrayDeque<>();
  8.         while (cur != null || !stack.isEmpty()) {
  9.             while (cur != null) {
  10.                 stack.push(cur);
  11.                 cur = cur.left;
  12.             }
  13.             TreeNode top = stack.pop();
  14.             System.out.print(top.val + " ");
  15.             cur = top.right;
  16.         }
  17.         System.out.println();
  18.     }

3️⃣后序遍历(Postorder Traversal)——根的左子树--->根的右子树--->根节点

  1.     //后序遍历
  2.     public void postOrder(TreeNode root) {
  3.         if(root == null) {
  4.             return;
  5.         }
  6.         postOrder(root.left);
  7.         postOrder(root.right);
  8.         System.out.println(root.val + " ");
  9.     }
  1.     //后序遍历非递归
  2.     public void postOrderNor(TreeNode root) {
  3.         if(root == null) {
  4.             return;
  5.         }
  6.         TreeNode cur = root;
  7.         TreeNode prev = null;
  8.         Deque<TreeNode> stack = new ArrayDeque<>();
  9.         while (cur != null || !stack.isEmpty()) {
  10.             while (cur != null) {
  11.                 stack.push(cur);
  12.                 cur = cur.left;
  13.             }
  14.             TreeNode top = stack.peek();
  15.             if(top.right == null || top.right == prev) {
  16.                 System.out.print(top.val+" ");
  17.                 stack.pop();
  18.                 prev = top;
  19.             }else {
  20.                 cur = top.right;
  21.             }
  22.         }
  23.         System.out.println();
  24.     }

🏹4.二叉树的实现

1️⃣获取树中节点的个数

🔎左树的结点 + 右树的结点 + 1             遍历思路：遇到结点就+1

  1.     //子问题思路：
  2.     public int size(TreeNode root) {
  3.         if(root == null) {
  4.             return 0;
  5.         }
  6.         int leftSize = size(root.left);
  7.         int rightSize = size(root.right);
  8.         return leftSize + rightSize + 1;
  9.     }
  1.     //遍历思路：
  2.     public  int nodeSize;//静态成员变量
  3.     public void size2(TreeNode root) {
  4.         if(root == null) {
  5.             return ;
  6.         }
  7.         nodeSize++;
  8.         size2(root.left);
  9.         size2(root.right);
  10.     }

2️⃣获取叶子节点的个数

🔎左树的叶子结点 + 右树的结点       

  1.     // 获取叶子节点的个数——子问题思路
  2.     int getLeafNodeCount(TreeNode root) {
  3.         if(root == null) {
  4.             return 0;
  5.         }
  6.         if(root.left == null && root.right == null){
  7.             return 1;
  8.         }
  9.         int leftSize = getLeafNodeCount(root.left);
  10.         int rightSize = getLeafNodeCount(root.right);
  11.         return leftSize+rightSize;
  12.     }
  1.     // 获取叶子节点的个数——遍历思路
  2.     public int leafSize;
  3.     void getLeafNodeCount2(TreeNode root) {
  4.         if(root == null) {
  5.             return ;
  6.         }
  7.         if(root.left == null && root.right == null){
  8.             leafSize++;
  9.         }
  10.         getLeafNodeCount2(root.left);
  11.         getLeafNodeCount2(root.right);
  12.     }

3️⃣获取第K层节点的个数

🔎左树的第k-1层  +  右树的第k-1层（对于root来说是第k层）

  1.     // 获取第K层节点的个数
  2.     int getKLevelNodeCount(TreeNode root,int k) {
  3.         if(root == null) {
  4.             return 0;
  5.         }
  6.         if(k == 1) {
  7.             return 1;
  8.         }
  9.         int leftSize = getKLevelNodeCount(root.left,k-1);
  10.         int rightSize = getKLevelNodeCount(root.right,k-1);
  11.         return leftSize+rightSize;
  12.     }

4️⃣获取二叉树的高度

🔎左树的高度和右树的高度的最大值+1

  1.     public int getHeight(TreeNode root) {
  2.         if(root == null) {
  3.             return 0;
  4.         }
  5.  
  6.         int leftHeight = getHeight(root.left);
  7.         int rightHeight = getHeight(root.right);
  8.  
  9.         return (leftHeight > rightHeight) ? (leftHeight+1) : (rightHeight+1);
  10.     }

5️⃣检测值为value的元素是否存在

🔎遍历二叉树，是否存在value的元素——前序

  1.     // 检测值为value的元素是否存在
  2.     TreeNode find(TreeNode root, int val) {
  3.         if(root == null) {
  4.             return null;
  5.         }
  6.         if(root.val == val) {
  7.             return root;
  8.         }
  9.         TreeNode leftTree = find(root.left,val);//左子树第一个元素为新的root，开始寻找value
  10.         //如果没有找到，继续递归；如果找到返回上一层直到返回这个值；如果左子树没有找到返回空
  11.         if(leftTree != null) {
  12.             return leftTree;
  13.         }
  14.         TreeNode rightTree = find(root.right,val);
  15.         if(rightTree != null) {
  16.             return rightTree;
  17.         }
  18.         return null;//没有找到
  19.     }

6️⃣判断两棵树是否相同【leetcod】

🔎leetcod题目：给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

👉题目链接：相同的树

💡做题思路：判断根，左子树、右子树是否相同——1.判断结构是否相同     2.判断val是否相同

  1.     /**
  2.      * 时间复杂度：O(min(m,n))，其中 m 和 n 分别是两个二叉树的节点数。
  3.      * 两个二叉树同时进行深度优先搜索，只有当两个二叉树中的对应节点都不为空时才会访问到该节点，因此被访问到的节点数不会超过较小的二叉树节点数
  4.      * 空间复杂度：O(min(m,n))，其中 m 和 n 分别是两个二叉树的节点数。
  5.      * 空间复杂度取决于递归调用的层数，递归调用的层数不会超过较小的二叉树的最大高度，最坏情况下，二叉树的高度等于节点数。
  6.      * @param p
  7.      * @param q
  8.      * @return
  9.      */
  10.     public boolean isSameTree(TreeNode p, TreeNode q) {
  11.         if(p == null && q != null || p != null && q == null) {
  12.             return false;
  13.         }
  14.         //走到这里 要么都是空 要么都不是空
  15.         if(p == null && q == null) {
  16.             return true;
  17.         }
  18.         if(p.val != q.val) {
  19.             return false;
  20.         }
  21.         //p q都不空 且 值一样
  22.         return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
  23.     }

7️⃣另一棵树的子树【leetcod】

🔎leetcod题目：给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

👉题目链接：另一棵树的子树

💡做题思路：1.是不是相同的树    2.是不是root的左子树  3.是不是root的右子树

  1.     public boolean isSubtree(TreeNode root, TreeNode subRoot) {
  2.         if(root == null || subRoot == null) {
  3.             return false;
  4.         }
  5.         if(isSameTree(root,subRoot)) return true;
  6.         if(isSubtree(root.left,subRoot)) return true;
  7.         if(isSubtree(root.right,subRoot)) return true;
  8.         return false;
  9.     }
  10.  
  11.     //判断相同的树
  12.     public boolean isSameTree(TreeNode p, TreeNode q) {
  13.         if(p != null && q == null || p == null && q != null) {
  14.             return false;
  15.         }
  16.         if(p == null && q == null) {
  17.             return true;
  18.         }
  19.         if(p.val != q.val) {
  20.             return false;
  21.         }
  22.         return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
  23.     }

8️⃣翻转二叉树【leetcod】

🔎leetcod题目：给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

👉题目链接：翻转二叉树

💡做题思路：

  1.     public TreeNode invertTree(TreeNode root) {
  2.         if(root == null) {
  3.             return null;
  4.         }
  5.         //交换左右结点
  6.         TreeNode tmp = root.left;
  7.         root.left = root.right;
  8.         root.right = tmp;
  9.  
  10.         invertTree(root.left);//左树递归
  11.         invertTree(root.right);//右树递归
  12.  
  13.         return root;
  14.     }

9️⃣平衡二叉树【leetcod】

🔎leetcod题目：给定一个二叉树，判断它是否是高度平衡的二叉树。本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

👉题目链接：平衡二叉树

💡做题思路：1.求整棵树的高度    2.左树高度和右树高度的绝对值之差小于2

  1.     /**
  2.      * 时间复杂度：O(N^2)——每个结点都需要求高度
  3.      * @param root
  4.      * @return
  5.      */
  6.     public boolean isBalanced(TreeNode root) {
  7.         if(root == null) {
  8.             return true;
  9.         }
  10.         //求左树和右树的高度
  11.         int leftH = getHeight(root.left);
  12.         int rightH = getHeight(root.right);
  13.         //左树和右树绝对值之差小于2
  14.         return Math.abs(leftH-rightH) < 2 && isBalanced(root.left) &&isBalanced(root.right);
  15.     }
  16.  
  17.     // 获取二叉树的高度
  18.     public int getHeight(TreeNode root) {
  19.         if(root == null) {
  20.             return 0;
  21.         }
  22.  
  23.         int leftHeight = getHeight(root.left);
  24.         int rightHeight = getHeight(root.right);
  25.  
  26.         return (leftHeight > rightHeight) ? (leftHeight+1) : (rightHeight+1);
  27.     }
  1.     /**
  2.      * 时间复杂度：O(N)——求高度的过程中就判断是否平衡
  3.      * @param root
  4.      * @return
  5.      */
  6.     public boolean isBalanced2(TreeNode root) {
  7.         return maxDepth2(root) >= 0;
  8.     }
  9.  
  10.     public int maxDepth2(TreeNode root) {
  11.         if(root == null) {
  12.             return 0;
  13.         }
  14.         int leftHeight = maxDepth2(root.left);
  15.         if(leftHeight < 0) return -1;
  16.  
  17.         int rightHeight = maxDepth2(root.right);
  18.         if(rightHeight < 0) return -1;
  19.  
  20.         if(Math.abs(leftHeight-rightHeight) <= 1) {
  21.             return Math.max(leftHeight,rightHeight)+1;
  22.         }else {
  23.             return -1;
  24.         }
  25.     }

🔟平衡二叉树【leetcod】

🔎leetcod题目：给你一个二叉树的根节点 root ， 检查它是否轴对称。

👉题目链接：平衡二叉树

💡做题思路：判断整棵树是不是抽对称的——判断左子树和右子树是不是对称的——左子树的左树和右子树的右树、左子树的右树和右子树的左树

  1.     public boolean isSymmetric(TreeNode root) {
  2.         if(root == null) {
  3.             return true;
  4.         }
  5.         return isSymmetricChild(root.left,root.right);
  6.     }
  7.  
  8.     public boolean isSymmetricChild(TreeNode leftTree,TreeNode rightTree) {
  9.         if(leftTree != null && rightTree == null || leftTree == null && rightTree != null) {
  10.             return false;
  11.         }
  12.         if(leftTree == null && rightTree == null) {
  13.             return true;
  14.         }
  15.         if(leftTree.val != rightTree.val) {
  16.             return false;
  17.         }
  18.         return isSymmetricChild(leftTree.left,rightTree.right) && isSymmetricChild(leftTree.right,rightTree.left);
  19.     }

⏸二叉树的层序遍历

💡做题思路：使用队列进行遍历：定义一个cur——从根结点出发，放入队列中，判断队列是否为空，不为空弹出队列的第一个元素，放入cur然后打印；然后把cur的左边和右边放入队列中，判断队列是否为空，不为空再弹出队列的队头（每次弹出1个元素），再放入cur中打印。一直循环直到遍历完成结束

  1.     //二叉树的层序遍历
  2.     public void levelOrder(TreeNode root) {
  3.         if(root == null) {
  4.             return;
  5.         }
  6.         Queue<TreeNode> queue = new LinkedList<>();
  7.         queue.offer(root);
  8.         while(!queue.isEmpty()) {
  9.             TreeNode cur = queue.poll();//不等于空，弹出
  10.             System.out.println(cur.val + " ");
  11.             if(cur.left != null) {
  12.                 queue.offer(cur.left);
  13.             }
  14.             if(cur.right != null) {
  15.                 queue.offer(cur.right);
  16.             }
  17.         }
  18.     }

二叉树的分层遍历【leetcod】

🔎leetcod题目：给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）

👉题目链接：二叉树的分层遍历

💡做题思路：每一层都是一个集合——得确定哪一层有哪些结点：如果队列不等于空，求当前队列的长度，这次弹出元素为当前队列长度的元素

  1.     public List<List<Integer>> levelOrder2(TreeNode root) {
  2.         List<List<Integer>> list = new ArrayList<>();
  3.         if(root == null) {
  4.             return list;
  5.         }
  6.  
  7.         Queue<TreeNode> queue = new LinkedList<>();
  8.         queue.offer(root);
  9.         while (!queue.isEmpty()) {
  10.             int size = queue.size();
  11.             List<Integer> tmp = new ArrayList<>();
  12.             while (size != 0) {
  13.                 TreeNode cur = queue.poll();
  14.                 //System.out.print(cur.val + " ");
  15.                 tmp.add(cur.val);
  16.                 size--;
  17.                 if (cur.left != null) {
  18.                     queue.offer(cur.left);
  19.                 }
  20.                 if (cur.right != null) {
  21.                     queue.offer(cur.right);
  22.                 }
  23.             }
  24.             list.add(tmp);
  25.         }
  26.         return list;
  27.     }

📜5.二叉树的练习

1️⃣二叉树遍历【牛客网】

🔎牛客网题目：编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。

输入描述：输入包括1行字符串，长度不超过100。

输出描述：可能有多组测试数据，对于每组数据， 输出将输入字符串建立二叉树后中序遍历的序列，每个字符后面都有一个空格。 每个输出结果占一行

输入：abc##de#g##f###          输出：c b e g d f a

👉题目链接：二叉树遍历

 💡做题思路：

  1. class TreeNode {
  2.     public char val;//数据域
  3.     public TreeNode left;//左孩子的引用
  4.     public TreeNode right;//右孩子的引用
  5.  
  6.     //构造函数
  7.     public TreeNode(char val) {
  8.          this.val = val;
  9.     }
  10. }
  11.  
  12. // 注意类名必须为 Main, 不要有任何 package xxx 信息
  13. public class Main {
  14.     public static void main(String[] args) {
  15.         Scanner in = new Scanner(System.in);
  16.         // 注意 hasNext 和 hasNextLine 的区别
  17.         while(in.hasNextLine()) {
  18.             String str =  in.nextLine();//读字符串放入str中
  19.             TreeNode root = createTree(str);
  20.             inorder(root);
  21.         }
  22.  
  23.     }
  24.  
  25.     public static int i = 0;
  26.  
  27.  
  28.     //读到字符串，紧接着来创造二叉树
  29.     public static TreeNode createTree(String str) {
  30.         TreeNode root = null;
  31.         if(str.charAt(i) != '#') {//查看i下标的值是字符还是#
  32.             root = new TreeNode(str.charAt(i));//创建一个节点为根
  33.             i++;
  34.             root.left = createTree(str);
  35.             root.right = createTree(str);
  36.         }else {
  37.             i++;//如果为#，则继续往后走一格
  38.         }
  39.         return root;
  40.         //1.如果为#，则继续往后走一格，返回上一层递归返回root
  41.         //2.如果根的左边和右边都为空，则返回当前根给上一层
  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. }

2️⃣二叉树的最近公共祖先【leetcod】

🔎leetcod题目：给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

👉题目链接：二叉树的最近公共祖先

 💡做题思路：1.p、q要么在跟的左右两边、2.要么是根的左边 或者 右边、3.其中一个节点是公共祖先

  1.     public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
  2.         if(root == null) {
  3.             return null;
  4.         }
  5.         //判断根结点是不是其中一个公共结点
  6.         if(root == p || root == q) {
  7.             return root;
  8.         }
  9.         TreeNode leftRet = lowestCommonAncestor(root.left,p,q);//去root的左边找p、q
  10.         TreeNode rightRet = lowestCommonAncestor(root.right,p,q);//去root的右边找p、q
  11.  
  12.         if(leftRet != null && rightRet != null) {//root的左边和右边不为空即返回root——1.root为根 2.root为左边根
  13.             return root;
  14.         }else if(leftRet != null) {
  15.             return leftRet;
  16.         }else if(rightRet != null) {
  17.             return rightRet;
  18.         }
  19.         return null;
  20.     }

第二种 ——💡做题思路：如果每个结点有了父亲结点的地址，那么这个题就变成了求相交结点——此时我们可以使用栈

从根结点到指定的p、q路径上的所有结点放入不同的两个栈中，求栈中元素的个数差，哪个栈多几个元素，就让哪个栈中弹出个数差的元素；之后让每个栈中都弹出一个元素比较两个元素是否相同，如果相同则为公共结点

❗❗❗难点： 如何把从根节点到指定节点，路径上的所有节点找到，放入栈里边？怎么知道这个节点要弹出去？

💡：从根节点开始放入第一个栈中，从根节点的左边开始，每个元素放入栈中，直到某个元素的左边和右边为null，弹出这个元素，然后从这个元素的右边去找，找不到则弹出此元素，直到找到为止

  1.     /**
  2.      *  找到从根节点到指定节点node路径上的所有的节点，存放到栈当中
  3.      * @param root
  4.      * @param node
  5.      * @param stack
  6.      * @return
  7.      */
  8.     //找p、q节点
  9.     public boolean getPath(TreeNode root, TreeNode node, Deque<TreeNode> stack) {
  10.         if(root == null || node == null) {
  11.             return false;
  12.         }
  13.         stack.push(root);
  14.         //放完之后  要检查
  15.         if(root == node) {
  16.             return true;
  17.         }
  18.         boolean ret1 = getPath(root.left,node,stack);
  19.         if(ret1) {
  20.             return true;
  21.         }
  22.         boolean ret2 = getPath(root.right,node,stack);
  23.         if(ret2) {
  24.             return true;
  25.         }
  26.         stack.pop();//如果没有找到，弹出这个元素，返回上一层
  27.         return false;
  28.     }
  29.  
  30.     
  31.     public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
  32.         //1、两个栈当中 存储好数据
  33.         Deque<TreeNode> stack1 = new LinkedList<>();//第一个栈
  34.         getPath(root,p,stack1);
  35.         Deque<TreeNode> stack2 = new LinkedList<>();//第二个栈
  36.         getPath(root,q,stack2);
  37.         //2.判断栈的大小
  38.         int size1 = stack1.size();
  39.         int size2 = stack2.size();
  40.         if(size1 > size2) {
  41.             int size = size1 - size2;
  42.             while(size != 0) {
  43.                 stack1.pop();//弹出元素，直到size为0；
  44.                 size--;
  45.             }
  46.         }else {
  47.             int size = size2 - size1;
  48.             while(size != 0) {
  49.                 stack2.pop();//弹出元素，直到size为0；
  50.                 size--;
  51.             }
  52.         }
  53.         //此时栈里面数据的个数 是一样的
  54.         while(!stack1.isEmpty() && !stack2.isEmpty()) {
  55.             if(stack1.peek() != stack2.peek()) {//查看栈顶元素是否相同
  56.                 //不同弹出栈顶元素
  57.                 stack1.pop();
  58.                 stack2.pop();
  59.             }else {
  60.                 return stack1.peek();//相同返回这个元素，即为公共节点
  61.             }
  62.         }
  63.         return null;
  64.  
  65.     }

3️⃣从前序与中序遍历序列构造二叉树【leetcod】

🔎leetcod题目：给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

👉题目链接：从前序与中序遍历序列构造二叉树

 💡做题思路：1.根据前序遍历找到根        2.在中序遍历当中，找到根的位置

  1.     public int i = 0;
  2.     public TreeNode buildTree(int[] preorder, int[] inorder) {
  3.         return buildTreeChild(preorder,inorder,0,inorder.length-1);
  4.     }
  5.     public TreeNode buildTreeChild(int[] preorder,int[] inorder,int inbegin,int inend) {
  6.         if(inbegin > inend) {
  7.             return null;//没有子树了
  8.         }
  9.         TreeNode root = new TreeNode(preorder[i]);
  10.  
  11.         //找到当前根，在中序遍历的位置
  12.         int rootIndex = findIndex(inorder,inbegin,inend,preorder[i]);//在inbegin和inend寻找preorder[i]
  13.         //找打根之后，左边就是左树，右边就是右树
  14.         i++;
  15.         //此时的根左边——开始位置没有变，结束位置为找到根位置-1，即rootIndex-1
  16.         root.left = buildTreeChild(preorder,inorder,inbegin,rootIndex-1);
  17.         //此时的根右边——开始位置为rootIndex+1，结束位置没有变
  18.         root.right = buildTreeChild(preorder,inorder,rootIndex+1,inend);
  19.  
  20.         return root;
  21.     }
  22.     //在中序遍历当中寻找这个元素
  23.     private int findIndex(int[] inorder,int inbegin, int inend, int key) {
  24.         for(int i = inbegin; i <= inend; i++) {
  25.             if(inorder[i] == key) {
  26.                 return i;
  27.             }
  28.         }
  29.         return -1;
  30.     }

4️⃣从中序与后序遍历序列构造二叉树【leetcod】

🔎leetcod题目：给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

👉题目链接：从中序与后序遍历序列构造二叉树

 💡做题思路：此题做题思路和上一题大致一样，但是有一点小问题，就是从后序遍历的结尾开始往前走，先创建右树，再创建左树

前序遍历：根、左、右             后序遍历：左、右、根

  1. public int i = 0;
  2.     public TreeNode buildTree1(int[] inorder, int[] postorder) {
  3.         i = postorder.length-1;//从最后开始
  4.         return buildTreeChild2(postorder,inorder,0,inorder.length-1);
  5.     }
  6.  
  7.     public TreeNode buildTreeChild2(int[] postorder, int[] inorder,
  8.                                     int inbegin,int inend) {
  9.         if(inbegin > inend) {
  10.             return null;//没有子树了
  11.         }
  12.         TreeNode root = new TreeNode(postorder[i]);
  13.         //找到当前根，在后序遍历的位置
  14.         int rootIndex = findIndex1(inorder,inbegin,inend,postorder[i]);
  15.         //找打根之后，左边就是左树，右边就是右树
  16.         i--;
  17.         //此时的根右边——开始位置为rootIndex+1，结束位置没有变
  18.         root.right = buildTreeChild2(postorder,inorder,rootIndex+1,inend);
  19.         //此时的根左边——开始位置没有变，结束位置为找到根位置-1，即rootIndex-1
  20.         root.left = buildTreeChild2(postorder,inorder,inbegin,rootIndex-1);
  21.         return root;
  22.     }
  23.     //在后序遍历当中寻找这个元素
  24.     private int findIndex1( int[] inorder,int inbegin,int inend, int key) {
  25.         for(int i = inbegin;i <= inend; i++) {
  26.             if(inorder[i] == key) {
  27.                 return i;
  28.             }
  29.         }
  30.         return -1;
  31.     }

5️⃣根据二叉树创建字符串【leetcod】

🔎leetcod题目：给你二叉树的根节点 root ，请你采用前序遍历的方式，将二叉树转化为一个由括号和整数组成的字符串，返回构造出的字符串。

空节点使用一对空括号对 "()" 表示，转化后需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。

输入：root = [1,2,3,4] 输出："1(2(4))(3)" 解释：初步转化后得到 "1(2(4)())(3()())" ，但省略所有不必要的空括号对后，字符串应该是"1(2(4))(3)"

👉题目链接：根据二叉树创建字符串

 💡做题思路：

  1.     public String tree2str(TreeNode root) {
  2.         if(root == null) {
  3.             return null;
  4.         }
  5.         StringBuilder stringBuilder = new StringBuilder();
  6.         tree2strChilde(root,stringBuilder);
  7.  
  8.         return stringBuilder.toString();
  9.     }
  10.     public void tree2strChilde(TreeNode t,StringBuilder stringBuilder) {
  11.  
  12.         if (t == null) {
  13.             return;
  14.         }
  15.  
  16.         stringBuilder.append(t.val);
  17.         if (t.left != null) {
  18.             stringBuilder.append("(");
  19.             tree2strChilde(t.left, stringBuilder);
  20.             stringBuilder.append(")");
  21.         } else {
  22.             //左边为空了
  23.             if (t.right != null) {
  24.                 //右边不为空
  25.                 stringBuilder.append("()");
  26.             } else {
  27.                 //右边为空
  28.                 return;
  29.             }
  30.         }
  31.  
  32.         if (t.right == null) {
  33.             return;
  34.         } else {
  35.             stringBuilder.append("(");
  36.             tree2strChilde(t.right, stringBuilder);
  37.             stringBuilder.append(")");
  38.         }
  39.     }

6️⃣判断一棵树是不是完全二叉树

💡做题思路：使用队列完成——把根放入队列当中，如果队列不为空，弹出一个元素给cur，不管左边、右边是否为空，把左子树和右子树都放入队列中（如果为空，放入null），如果队列不为空，继续弹出一个元素给cur，循环，直到cur里边放入null。这是队列中如果不为空，则不是二叉树，如果为空，则为二叉树

 

  1.     boolean isCompleteTree(TreeNode root){
  2.         if(root == null) {
  3.             return true;
  4.         }
  5.         //创建队列
  6.         Queue<TreeNode> queue = new LinkedList<>();
  7.         queue.offer(root);
  8.         while (!queue.isEmpty()) {
  9.             TreeNode cur = queue.poll();
  10.             if(cur != null) {
  11.                 queue.offer(cur.left);
  12.                 queue.offer(cur.right);
  13.             }else {
  14.                 break;
  15.             }
  16.         }
  17.         while (!queue.isEmpty()) {
  18.             TreeNode tmp = queue.poll();
  19.             if(tmp != null) {
  20.                 return false;
  21.             }
  22.         }
  23.         return true;
  24.     }

 

 

 

文章知识点与官方知识档案匹配，可进一步学习相关知识
算法技能树首页概览48445 人正在系统学习中
【算法系列篇】滑动窗口
走进人工智能|深度学习 算法的创世纪