目录
结点的度：一个结点含有子树的个数称为该结点的度； 如上图：A的度为2
树的度：一棵树中，所有结点度的最大值称为树的度； 如上图：树的度为2
叶子结点或终端结点：度为0的结点称为叶结点； 如上图：H、I、J、K、G等节点为叶结点
双亲结点或父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点； 如上图：A是B的父结点
孩子结点或子结点：一个结点含有的子树的根结点称为该结点的子结点； 如上图：B是A的孩子结点
根结点：一棵树中，没有双亲结点的结点；如上图：A
结点的层次：从根开始定义起，根为第1层，根的子结点为第2层，以此类推
树的高度或深度：树中结点的最大层次； 如上图：树的高度为4
📑一棵二叉树是结点的一个有限集合，该集合：
1️⃣或者为空 2️⃣或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成。
✨对于二叉树来说：每一个节点的度不能大于2，并且二叉树是一个有序树
满二叉树: 一棵二叉树，如果每层的结点数都达到最大值，则这棵二叉树就是满二叉树。也就是说，如果一棵二叉树的层数为K，且结点总数是 2^k - 1，第k层节点数是 2^(k-1) ,则它就是满二叉树。如果一共有n个节点，那么k=log2（n+1）
完全二叉树（最小深度）: 完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从0至n-1的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。——从左往右不可以空结点
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
✨对于一个二叉树，我们定义一个数据域、左孩子域、右孩子域、根结点。对于一个二叉树，如图所示，总会有一个左结点和右结点（可以为null）
//创建二叉树
public class TreeNode {
public char val;//数据域
public TreeNode left;//左孩子的引用
public TreeNode right;//右孩子的引用
//构造函数
public TreeNode(char val) {
this.val = val;
}
}
public TreeNode root;//二叉树的根结点
public TreeNode createTree() {
TreeNode A = new TreeNode('A');
TreeNode B = new TreeNode('B');
TreeNode C = new TreeNode('C');
TreeNode D = new TreeNode('D');
TreeNode E = new TreeNode('E');
TreeNode F = new TreeNode('F');
TreeNode G = new TreeNode('G');
TreeNode H = new TreeNode('H');
A.left = B;
A.right = C;
B.left = D;
B.right = E;
C.left = F;
C.right = G;
E.right = H;
this.root = A;
return root;
}遍历：历(Traversal)是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题(比如：打印节点内容、节点内容加1)。
1️⃣前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点--->根的左子树--->根的右子树
❗注意：每棵树都有根、左、右结点。并且这里边每个结点都可以作为孩子结点的根结点
//前序遍历 递归
public void preOrder(TreeNode root) {
if(root == null) {
return;
}
System.out.println(root.val + " ");//先打印再递归
preOrder(root.left);
preOrder(root.right);
}非递归实现二叉树的前序遍历：使用栈完成——定义一个cur = root，把根节点放入栈中，同时进行打印，把根左边放入栈中，再进行打印，继续往左边走放入栈中，再进行打印；再往左边走，如果为null，则从栈中弹出这个元素给top；如果这个元素右边为null，则再弹出一个元素给top，循环以上过程
/非递归：
public void preOrderNor(TreeNode root) {
if(root == null) {
return;
}
TreeNode cur = root;
Deque<TreeNode> stack = new ArrayDeque<>();
while (cur != null || stack.isEmpty()) {
while (cur != null) {
stack.push(cur);
System.out.print(cur.val + " ");
cur = cur.left;
}
TreeNode top = stack.pop();
cur = top.right;
}
System.out.println();
}2️⃣中序遍历(Inorder Traversal)——根的左子树--->根节点--->根的右子树。
//中序遍历
public void inOrder(TreeNode root) {
if(root == null) {
return;
}
inOrder(root.left);
System.out.println(root.val + " ");
inOrder(root.right);
} //中序遍历非递归
public void inOrderNor(TreeNode root) {
if(root == null) {
return;
}
TreeNode cur = root;
Deque<TreeNode> stack = new ArrayDeque<>();
while (cur != null || !stack.isEmpty()) {
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
TreeNode top = stack.pop();
System.out.print(top.val + " ");
cur = top.right;
}
System.out.println();
}3️⃣后序遍历(Postorder Traversal)——根的左子树--->根的右子树--->根节点
//后序遍历
public void postOrder(TreeNode root) {
if(root == null) {
return;
}
postOrder(root.left);
postOrder(root.right);
System.out.println(root.val + " ");
} //后序遍历非递归
public void postOrderNor(TreeNode root) {
if(root == null) {
return;
}
TreeNode cur = root;
TreeNode prev = null;
Deque<TreeNode> stack = new ArrayDeque<>();
while (cur != null || !stack.isEmpty()) {
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
TreeNode top = stack.peek();
if(top.right == null || top.right == prev) {
System.out.print(top.val+" ");
stack.pop();
prev = top;
}else {
cur = top.right;
}
}
System.out.println();
}🔎左树的结点 + 右树的结点 + 1 遍历思路：遇到结点就+1
//子问题思路：
public int size(TreeNode root) {
if(root == null) {
return 0;
}
int leftSize = size(root.left);
int rightSize = size(root.right);
return leftSize + rightSize + 1;
} //遍历思路：
public int nodeSize;//静态成员变量
public void size2(TreeNode root) {
if(root == null) {
return ;
}
nodeSize++;
size2(root.left);
size2(root.right);
}🔎左树的叶子结点 + 右树的结点
// 获取叶子节点的个数——子问题思路
int getLeafNodeCount(TreeNode root) {
if(root == null) {
return 0;
}
if(root.left == null && root.right == null){
return 1;
}
int leftSize = getLeafNodeCount(root.left);
int rightSize = getLeafNodeCount(root.right);
return leftSize+rightSize;
} // 获取叶子节点的个数——遍历思路
public int leafSize;
void getLeafNodeCount2(TreeNode root) {
if(root == null) {
return ;
}
if(root.left == null && root.right == null){
leafSize++;
}
getLeafNodeCount2(root.left);
getLeafNodeCount2(root.right);
}🔎左树的第k-1层 + 右树的第k-1层（对于root来说是第k层）
// 获取第K层节点的个数
int getKLevelNodeCount(TreeNode root,int k) {
if(root == null) {
return 0;
}
if(k == 1) {
return 1;
}
int leftSize = getKLevelNodeCount(root.left,k-1);
int rightSize = getKLevelNodeCount(root.right,k-1);
return leftSize+rightSize;
}🔎左树的高度和右树的高度的最大值+1
public int getHeight(TreeNode root) {
if(root == null) {
return 0;
}
int leftHeight = getHeight(root.left);
int rightHeight = getHeight(root.right);
return (leftHeight > rightHeight) ? (leftHeight+1) : (rightHeight+1);
}🔎遍历二叉树，是否存在value的元素——前序
// 检测值为value的元素是否存在
TreeNode find(TreeNode root, int val) {
if(root == null) {
return null;
}
if(root.val == val) {
return root;
}
TreeNode leftTree = find(root.left,val);//左子树第一个元素为新的root，开始寻找value
//如果没有找到，继续递归；如果找到返回上一层直到返回这个值；如果左子树没有找到返回空
if(leftTree != null) {
return leftTree;
}
TreeNode rightTree = find(root.right,val);
if(rightTree != null) {
return rightTree;
}
return null;//没有找到
}🔎leetcod题目：给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
👉题目链接：相同的树
💡做题思路：判断根，左子树、右子树是否相同——1.判断结构是否相同 2.判断val是否相同
/**
* 时间复杂度：O(min(m,n))，其中 m 和 n 分别是两个二叉树的节点数。
* 两个二叉树同时进行深度优先搜索，只有当两个二叉树中的对应节点都不为空时才会访问到该节点，因此被访问到的节点数不会超过较小的二叉树节点数
* 空间复杂度：O(min(m,n))，其中 m 和 n 分别是两个二叉树的节点数。
* 空间复杂度取决于递归调用的层数，递归调用的层数不会超过较小的二叉树的最大高度，最坏情况下，二叉树的高度等于节点数。
* @param p
* @param q
* @return
*/
public boolean isSameTree(TreeNode p, TreeNode q) {
if(p == null && q != null || p != null && q == null) {
return false;
}
//走到这里 要么都是空 要么都不是空
if(p == null && q == null) {
return true;
}
if(p.val != q.val) {
return false;
}
//p q都不空 且 值一样
return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
}🔎leetcod题目：给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。
👉题目链接：另一棵树的子树
💡做题思路：1.是不是相同的树 2.是不是root的左子树 3.是不是root的右子树
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
if(root == null || subRoot == null) {
return false;
}
if(isSameTree(root,subRoot)) return true;
if(isSubtree(root.left,subRoot)) return true;
if(isSubtree(root.right,subRoot)) return true;
return false;
}
//判断相同的树
public boolean isSameTree(TreeNode p, TreeNode q) {
if(p != null && q == null || p == null && q != null) {
return false;
}
if(p == null && q == null) {
return true;
}
if(p.val != q.val) {
return false;
}
return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
}🔎leetcod题目：给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
👉题目链接：翻转二叉树
💡做题思路：
public TreeNode invertTree(TreeNode root) {
if(root == null) {
return null;
}
//交换左右结点
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;
invertTree(root.left);//左树递归
invertTree(root.right);//右树递归
return root;
}9️⃣平衡二叉树【leetcod】
🔎leetcod题目：给定一个二叉树，判断它是否是高度平衡的二叉树。本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
👉题目链接：平衡二叉树
💡做题思路：1.求整棵树的高度 2.左树高度和右树高度的绝对值之差小于2
/**
* 时间复杂度：O(N^2)——每个结点都需要求高度
* @param root
* @return
*/
public boolean isBalanced(TreeNode root) {
if(root == null) {
return true;
}
//求左树和右树的高度
int leftH = getHeight(root.left);
int rightH = getHeight(root.right);
//左树和右树绝对值之差小于2
return Math.abs(leftH-rightH) < 2 && isBalanced(root.left) &&isBalanced(root.right);
}
// 获取二叉树的高度
public int getHeight(TreeNode root) {
if(root == null) {
return 0;
}
int leftHeight = getHeight(root.left);
int rightHeight = getHeight(root.right);
return (leftHeight > rightHeight) ? (leftHeight+1) : (rightHeight+1);
} /**
* 时间复杂度：O(N)——求高度的过程中就判断是否平衡
* @param root
* @return
*/
public boolean isBalanced2(TreeNode root) {
return maxDepth2(root) >= 0;
}
public int maxDepth2(TreeNode root) {
if(root == null) {
return 0;
}
int leftHeight = maxDepth2(root.left);
if(leftHeight < 0) return -1;
int rightHeight = maxDepth2(root.right);
if(rightHeight < 0) return -1;
if(Math.abs(leftHeight-rightHeight) <= 1) {
return Math.max(leftHeight,rightHeight)+1;
}else {
return -1;
}
}🔎leetcod题目：给你一个二叉树的根节点 root ， 检查它是否轴对称。
👉题目链接：平衡二叉树
💡做题思路：判断整棵树是不是抽对称的——判断左子树和右子树是不是对称的——左子树的左树和右子树的右树、左子树的右树和右子树的左树
public boolean isSymmetric(TreeNode root) {
if(root == null) {
return true;
}
return isSymmetricChild(root.left,root.right);
}
public boolean isSymmetricChild(TreeNode leftTree,TreeNode rightTree) {
if(leftTree != null && rightTree == null || leftTree == null && rightTree != null) {
return false;
}
if(leftTree == null && rightTree == null) {
return true;
}
if(leftTree.val != rightTree.val) {
return false;
}
return isSymmetricChild(leftTree.left,rightTree.right) && isSymmetricChild(leftTree.right,rightTree.left);
}💡做题思路：使用队列进行遍历：定义一个cur——从根结点出发，放入队列中，判断队列是否为空，不为空弹出队列的第一个元素，放入cur然后打印；然后把cur的左边和右边放入队列中，判断队列是否为空，不为空再弹出队列的队头（每次弹出1个元素），再放入cur中打印。一直循环直到遍历完成结束
//二叉树的层序遍历
public void levelOrder(TreeNode root) {
if(root == null) {
return;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()) {
TreeNode cur = queue.poll();//不等于空，弹出
System.out.println(cur.val + " ");
if(cur.left != null) {
queue.offer(cur.left);
}
if(cur.right != null) {
queue.offer(cur.right);
}
}
}🔎leetcod题目：给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）
👉题目链接：二叉树的分层遍历
💡做题思路：每一层都是一个集合——得确定哪一层有哪些结点：如果队列不等于空，求当前队列的长度，这次弹出元素为当前队列长度的元素
public List<List<Integer>> levelOrder2(TreeNode root) {
List<List<Integer>> list = new ArrayList<>();
if(root == null) {
return list;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
List<Integer> tmp = new ArrayList<>();
while (size != 0) {
TreeNode cur = queue.poll();
//System.out.print(cur.val + " ");
tmp.add(cur.val);
size--;
if (cur.left != null) {
queue.offer(cur.left);
}
if (cur.right != null) {
queue.offer(cur.right);
}
}
list.add(tmp);
}
return list;
}🔎牛客网题目：编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。
输入描述：输入包括1行字符串，长度不超过100。
输出描述：可能有多组测试数据，对于每组数据， 输出将输入字符串建立二叉树后中序遍历的序列，每个字符后面都有一个空格。 每个输出结果占一行
输入：abc##de#g##f### 输出：c b e g d f a
👉题目链接：二叉树遍历
💡做题思路：
class TreeNode {
public char val;//数据域
public TreeNode left;//左孩子的引用
public TreeNode right;//右孩子的引用
//构造函数
public TreeNode(char val) {
this.val = val;
}
}
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
while(in.hasNextLine()) {
String str = in.nextLine();//读字符串放入str中
TreeNode root = createTree(str);
inorder(root);
}
}
public static int i = 0;
//读到字符串，紧接着来创造二叉树
public static TreeNode createTree(String str) {
TreeNode root = null;
if(str.charAt(i) != '#') {//查看i下标的值是字符还是#
root = new TreeNode(str.charAt(i));//创建一个节点为根
i++;
root.left = createTree(str);
root.right = createTree(str);
}else {
i++;//如果为#，则继续往后走一格
}
return root;
//1.如果为#，则继续往后走一格，返回上一层递归返回root
//2.如果根的左边和右边都为空，则返回当前根给上一层
}
//中序遍历
public static void inorder(TreeNode root) {
if(root == null) {
return;
}
inorder(root.left);
System.out.print(root.val + " ");
inorder(root.right);
}
}🔎leetcod题目：给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
👉题目链接：二叉树的最近公共祖先
💡做题思路：1.p、q要么在跟的左右两边、2.要么是根的左边 或者 右边、3.其中一个节点是公共祖先
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null) {
return null;
}
//判断根结点是不是其中一个公共结点
if(root == p || root == q) {
return root;
}
TreeNode leftRet = lowestCommonAncestor(root.left,p,q);//去root的左边找p、q
TreeNode rightRet = lowestCommonAncestor(root.right,p,q);//去root的右边找p、q
if(leftRet != null && rightRet != null) {//root的左边和右边不为空即返回root——1.root为根 2.root为左边根
return root;
}else if(leftRet != null) {
return leftRet;
}else if(rightRet != null) {
return rightRet;
}
return null;
}第二种 ——💡做题思路：如果每个结点有了父亲结点的地址，那么这个题就变成了求相交结点——此时我们可以使用栈
从根结点到指定的p、q路径上的所有结点放入不同的两个栈中，求栈中元素的个数差，哪个栈多几个元素，就让哪个栈中弹出个数差的元素；之后让每个栈中都弹出一个元素比较两个元素是否相同，如果相同则为公共结点
❗❗❗难点： 如何把从根节点到指定节点，路径上的所有节点找到，放入栈里边？怎么知道这个节点要弹出去？
💡：从根节点开始放入第一个栈中，从根节点的左边开始，每个元素放入栈中，直到某个元素的左边和右边为null，弹出这个元素，然后从这个元素的右边去找，找不到则弹出此元素，直到找到为止
/**
* 找到从根节点到指定节点node路径上的所有的节点，存放到栈当中
* @param root
* @param node
* @param stack
* @return
*/
//找p、q节点
public boolean getPath(TreeNode root, TreeNode node, Deque<TreeNode> stack) {
if(root == null || node == null) {
return false;
}
stack.push(root);
//放完之后 要检查
if(root == node) {
return true;
}
boolean ret1 = getPath(root.left,node,stack);
if(ret1) {
return true;
}
boolean ret2 = getPath(root.right,node,stack);
if(ret2) {
return true;
}
stack.pop();//如果没有找到，弹出这个元素，返回上一层
return false;
}
public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
//1、两个栈当中 存储好数据
Deque<TreeNode> stack1 = new LinkedList<>();//第一个栈
getPath(root,p,stack1);
Deque<TreeNode> stack2 = new LinkedList<>();//第二个栈
getPath(root,q,stack2);
//2.判断栈的大小
int size1 = stack1.size();
int size2 = stack2.size();
if(size1 > size2) {
int size = size1 - size2;
while(size != 0) {
stack1.pop();//弹出元素，直到size为0；
size--;
}
}else {
int size = size2 - size1;
while(size != 0) {
stack2.pop();//弹出元素，直到size为0；
size--;
}
}
//此时栈里面数据的个数 是一样的
while(!stack1.isEmpty() && !stack2.isEmpty()) {
if(stack1.peek() != stack2.peek()) {//查看栈顶元素是否相同
//不同弹出栈顶元素
stack1.pop();
stack2.pop();
}else {
return stack1.peek();//相同返回这个元素，即为公共节点
}
}
return null;
}🔎leetcod题目：给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
👉题目链接：从前序与中序遍历序列构造二叉树
💡做题思路：1.根据前序遍历找到根 2.在中序遍历当中，找到根的位置
public int i = 0;
public TreeNode buildTree(int[] preorder, int[] inorder) {
return buildTreeChild(preorder,inorder,0,inorder.length-1);
}
public TreeNode buildTreeChild(int[] preorder,int[] inorder,int inbegin,int inend) {
if(inbegin > inend) {
return null;//没有子树了
}
TreeNode root = new TreeNode(preorder[i]);
//找到当前根，在中序遍历的位置
int rootIndex = findIndex(inorder,inbegin,inend,preorder[i]);//在inbegin和inend寻找preorder[i]
//找打根之后，左边就是左树，右边就是右树
i++;
//此时的根左边——开始位置没有变，结束位置为找到根位置-1，即rootIndex-1
root.left = buildTreeChild(preorder,inorder,inbegin,rootIndex-1);
//此时的根右边——开始位置为rootIndex+1，结束位置没有变
root.right = buildTreeChild(preorder,inorder,rootIndex+1,inend);
return root;
}
//在中序遍历当中寻找这个元素
private int findIndex(int[] inorder,int inbegin, int inend, int key) {
for(int i = inbegin; i <= inend; i++) {
if(inorder[i] == key) {
return i;
}
}
return -1;
}🔎leetcod题目：给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
👉题目链接：从中序与后序遍历序列构造二叉树
💡做题思路：此题做题思路和上一题大致一样，但是有一点小问题，就是从后序遍历的结尾开始往前走，先创建右树，再创建左树
前序遍历：根、左、右 后序遍历：左、右、根
public int i = 0;
public TreeNode buildTree1(int[] inorder, int[] postorder) {
i = postorder.length-1;//从最后开始
return buildTreeChild2(postorder,inorder,0,inorder.length-1);
}
public TreeNode buildTreeChild2(int[] postorder, int[] inorder,
int inbegin,int inend) {
if(inbegin > inend) {
return null;//没有子树了
}
TreeNode root = new TreeNode(postorder[i]);
//找到当前根，在后序遍历的位置
int rootIndex = findIndex1(inorder,inbegin,inend,postorder[i]);
//找打根之后，左边就是左树，右边就是右树
i--;
//此时的根右边——开始位置为rootIndex+1，结束位置没有变
root.right = buildTreeChild2(postorder,inorder,rootIndex+1,inend);
//此时的根左边——开始位置没有变，结束位置为找到根位置-1，即rootIndex-1
root.left = buildTreeChild2(postorder,inorder,inbegin,rootIndex-1);
return root;
}
//在后序遍历当中寻找这个元素
private int findIndex1( int[] inorder,int inbegin,int inend, int key) {
for(int i = inbegin;i <= inend; i++) {
if(inorder[i] == key) {
return i;
}
}
return -1;
}🔎leetcod题目：给你二叉树的根节点 root ，请你采用前序遍历的方式，将二叉树转化为一个由括号和整数组成的字符串，返回构造出的字符串。
空节点使用一对空括号对 "()" 表示，转化后需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。
输入：root = [1,2,3,4] 输出："1(2(4))(3)" 解释：初步转化后得到 "1(2(4)())(3()())" ，但省略所有不必要的空括号对后，字符串应该是"1(2(4))(3)"
👉题目链接：根据二叉树创建字符串
💡做题思路：
public String tree2str(TreeNode root) {
if(root == null) {
return null;
}
StringBuilder stringBuilder = new StringBuilder();
tree2strChilde(root,stringBuilder);
return stringBuilder.toString();
}
public void tree2strChilde(TreeNode t,StringBuilder stringBuilder) {
if (t == null) {
return;
}
stringBuilder.append(t.val);
if (t.left != null) {
stringBuilder.append("(");
tree2strChilde(t.left, stringBuilder);
stringBuilder.append(")");
} else {
//左边为空了
if (t.right != null) {
//右边不为空
stringBuilder.append("()");
} else {
//右边为空
return;
}
}
if (t.right == null) {
return;
} else {
stringBuilder.append("(");
tree2strChilde(t.right, stringBuilder);
stringBuilder.append(")");
}
}💡做题思路：使用队列完成——把根放入队列当中，如果队列不为空，弹出一个元素给cur，不管左边、右边是否为空，把左子树和右子树都放入队列中（如果为空，放入null），如果队列不为空，继续弹出一个元素给cur，循环，直到cur里边放入null。这是队列中如果不为空，则不是二叉树，如果为空，则为二叉树
boolean isCompleteTree(TreeNode root){
if(root == null) {
return true;
}
//创建队列
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode cur = queue.poll();
if(cur != null) {
queue.offer(cur.left);
queue.offer(cur.right);
}else {
break;
}
}
while (!queue.isEmpty()) {
TreeNode tmp = queue.poll();
if(tmp != null) {
return false;
}
}
return true;
}我想将html转换为纯文本。不过，我不想只删除标签，我想智能地保留尽可能多的格式。为插入换行符标签，检测段落并格式化它们等。输入非常简单，通常是格式良好的html(不是整个文档，只是一堆内容，通常没有anchor或图像)。我可以将几个正则表达式放在一起，让我达到80%，但我认为可能有一些现有的解决方案更智能。 最佳答案 首先，不要尝试为此使用正则表达式。很有可能你会想出一个脆弱/脆弱的解决方案，它会随着HTML的变化而崩溃，或者很难管理和维护。您可以使用Nokogiri快速解析HTML并提取文本:require'nokogiri'h
我主要使用Ruby来执行此操作，但到目前为止我的攻击计划如下:使用gemsrdf、rdf-rdfa和rdf-microdata或mida来解析给定任何URI的数据。我认为最好映射到像schema.org这样的统一模式，例如使用这个yaml文件，它试图描述数据词汇表和opengraph到schema.org之间的转换:#SchemaXtoschema.orgconversion#data-vocabularyDV:name:namestreet-address:streetAddressregion:addressRegionlocality:addressLocalityphoto:i
有时我需要处理键/值数据。我不喜欢使用数组，因为它们在大小上没有限制(很容易不小心添加超过2个项目，而且您最终需要稍后验证大小)。此外，0和1的索引变成了魔数(MagicNumber)，并且在传达含义方面做得很差(“当我说0时，我的意思是head...”)。散列也不合适，因为可能会不小心添加额外的条目。我写了下面的类来解决这个问题:classPairattr_accessor:head,:taildefinitialize(h,t)@head,@tail=h,tendend它工作得很好并且解决了问题，但我很想知道:Ruby标准库是否已经带有这样一个类？ 最佳
给定一个复杂的对象层次结构，幸运的是它不包含循环引用，我如何实现支持各种格式的序列化？我不是来讨论实际实现的。相反，我正在寻找可能会派上用场的设计模式提示。更准确地说:我正在使用Ruby，我想解析XML和JSON数据以构建复杂的对象层次结构。此外，应该可以将该层次结构序列化为JSON、XML和可能的HTML。我可以为此使用Builder模式吗？在任何提到的情况下，我都有某种结构化数据-无论是在内存中还是文本中-我想用它来构建其他东西。我认为将序列化逻辑与实际业务逻辑分开会很好，这样我以后就可以轻松支持多种XML格式。 最佳答案 我最
我正在尝试使用Curbgem执行以下POST以解析云curl-XPOST\-H"X-Parse-Application-Id:PARSE_APP_ID"\-H"X-Parse-REST-API-Key:PARSE_API_KEY"\-H"Content-Type:image/jpeg"\--data-binary'@myPicture.jpg'\https://api.parse.com/1/files/pic.jpg用这个:curl=Curl::Easy.new("https://api.parse.com/1/files/lion.jpg")curl.multipart_form_
无论您是想搭建桌面端、WEB端或者移动端APP应用，HOOPSPlatform组件都可以为您提供弹性的3D集成架构，同时，由工业领域3D技术专家组成的HOOPS技术团队也能为您提供技术支持服务。如果您的客户期望有一种在多个平台（桌面/WEB/APP，而且某些客户端是“瘦”客户端）快速、方便地将数据接入到3D应用系统的解决方案，并且当访问数据时，在各个平台上的性能和用户体验保持一致，HOOPSPlatform将帮助您完成。利用HOOPSPlatform，您可以开发在任何环境下的3D基础应用架构。HOOPSPlatform可以帮您打造3D创新型产品，HOOPSSDK包含的技术有：快速且准确的CAD
本教程将在Unity3D中混合Optitrack与数据手套的数据流，在人体运动的基础上，添加双手手指部分的运动。双手手背的角度仍由Optitrack提供，数据手套提供双手手指的角度。 01 客户端软件分别安装MotiveBody与MotionVenus并校准人体与数据手套。MotiveBodyMotionVenus数据手套使用、校准流程参照：https://gitee.com/foheart_1/foheart-h1-data-summary.git02 数据转发打开MotiveBody软件的Streaming，开始向Unity3D广播数据；MotionVenus中设置->选项选择Unit
文章目录一、概述简介原理模块二、配置Mysql使用版本环境要求1.操作系统2.mysql要求三、配置canal-server离线下载在线下载上传解压修改配置单机配置集群配置分库分表配置1.修改全局配置2.实例配置垂直分库水平分库3.修改group-instance.xml4.启动监听四、配置canal-adapter1修改启动配置2配置映射文件3启动ES数据同步查询所有订阅同步数据同步开关启动4.验证五、配置canal-admin一、概述简介canal是Alibaba旗下的一款开源项目，Java开发。基于数据库增量日志解析，提供增量数据订阅&消费。Git地址：https://github.co
我正在尝试在Rails上安装ruby，到目前为止一切都已安装，但是当我尝试使用rakedb:create创建数据库时，我收到一个奇怪的错误:dyld:lazysymbolbindingfailed:Symbolnotfound:_mysql_get_client_infoReferencedfrom:/Library/Ruby/Gems/1.8/gems/mysql2-0.3.11/lib/mysql2/mysql2.bundleExpectedin:flatnamespacedyld:Symbolnotfound:_mysql_get_client_infoReferencedf
文章目录1.开发板选择*用到的资源2.串口通信（个人理解）3.代码分析（注释比较详细）1.主函数2.串口1配置3.串口2配置以及中断函数4.注意问题5.源码链接1.开发板选择我用的是STM32F103RCT6的板子，不过代码大概在F103系列的板子上都可以运行，我试过在野火103的霸道板上也可以，主要看一下串口对应的引脚一不一样就行了，不一样的就更改一下。*用到的资源keil5软件这里用到了两个串口资源，采集数据一个，串口通信一个，板子对应引脚如下：串口1，TX：PA9，RX：PA10串口2，TX：PA2，RX：PA32.串口通信（个人理解）我就从串口采集传感器数据这个过程说一下我自己的理解，