✨博客主页: 心荣~
✨系列专栏:【LeetCode/牛客刷题】
✨一句短话: 难在坚持,贵在坚持,成在坚持!
文章目录
在线OJ：100. 相同的树
给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
示例 1：
输入：p = [1,2,3], q = [1,2,3]
输出：true
示例 2：
输入：p = [1,2], q = [1,null,2]
输出：false
示例 3：
输入：p = [1,2,1], q = [1,1,2]
输出：false
提示：
💯解题思路:
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if(p == null && q == null) {// 1
return true;
}
if(p == null && q != null || p != null && q == null) {// 2
return false;
}
if(p.val != q.val) { // 3
return false;
}
// 4
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
}
在线OJ：572. 另一棵树的子树
给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true；否则，返回 false 。
二叉树 tree 的一棵子树包括tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。
示例 1：
输入：root = [3,4,5,1,2], subRoot = [4,1,2]
输出：true
示例 2：
输入：root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
输出：false
提示：
💯解题思路:
判断一棵树是否为另一棵树的子树我们可以基于判断两棵树是否相同去做。
class Solution {
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
if(root == null && subRoot != null || root != null && subRoot == null) {
return false; // 1
}
if(isSameTree(root, subRoot)) {
return true; // 2
}
if(isSubtree(root.left, subRoot)) { // 3
return true;
}
if(isSubtree(root.right, subRoot)) {
return true;
}
return false;
}
//判断两棵树是否相同
public boolean isSameTree(TreeNode p, TreeNode q) {
if(p == null && q == null) {
return true;
}
if(p == null && q != null || p != null && q == null) {
return false;
}
if(p.val != q.val) {
return false;
}
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
}
在线OJ：104. 二叉树的最大深度
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例：
给定二叉树 [3,9,20,null,null,15,7]，
3
/ \
9 20
/ \
15 7
返回它的最大深度 3 。
💯解题思路:
class Solution {
public int maxDepth(TreeNode root) {
if(root == null) { //1
return 0;
}
int leftHight = maxDepth(root.left);
int rightHight = maxDepth(root.right); //2
return leftHight>rightHight ? leftHight+1 : rightHight+1;
}
}
在线OJ：110. 平衡二叉树
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：true
示例 2：
输入：root = [1,2,2,3,3,null,null,4,4]
输出：false
示例 3：
输入：root = []
输出：true
提示：
💯解题思路:
这道题可以基于求二叉树的高度来做,
class Solution {
//写法二:写法一优化
//如果有子树不满足平衡二叉树, 就返回树的高度为-1
//与写法一相比,避免了重复递归子树
public boolean isBalanced(TreeNode root) {
if(root == null) {
return true;
}
return maxDepth(root) >= 0;
}
public int maxDepth(TreeNode root) {
if(root == null) {
return 0;
}
int leftHight = maxDepth(root.left);
int rightHight = maxDepth(root.right);
if(leftHight >= 0 && rightHight >= 0 &&
Math.abs(leftHight - rightHight) <= 1) {
return Math.max(leftHight, rightHight) + 1;
}else {
return -1;
}
}
//写法一:
/*public boolean isBalanced(TreeNode root) {
if(root == null) { // 1
return true;
}
int leftHight = maxDepth(root.left);
int rightHight = maxDepth(root.right);
return Math.abs(leftHight-rightHight) < 2 // 2
&& isBalanced(root.left)
&& isBalanced(root.right); // 3
}
//求二叉树的高度
public int maxDepth(TreeNode root) {
if(root == null) {
return 0;
}
int leftHight = maxDepth(root.left);
int rightHight = maxDepth(root.right);
return leftHight>rightHight ? leftHight+1 : rightHight+1;
}
*/
}
在线OJ：101. 对称二叉树
给你一个二叉树的根节点 root， 检查它是否轴对称。
示例 1：
输入：root = [1,2,2,3,4,4,3]
输出：true
示例 2：
输入：root = [1,2,2,null,3,null,3]
输出：false
提示：
💯解题思路:
(1)判断左右子树两个根节点值是否相等
(2)判断 A(左) 的右子树与 B(右) 的左子树是否对称(递归)
(3)判断 A(左) 的左子树与 B 的右子树是否对称(递归)
(1)左右子树两个根节点值不相等
(2)都为空指针则返回 true
(3)只有一个为空则返回 false
class Solution {
public boolean isSymmetric(TreeNode root) {
if(root == null) {// 1
return true;
}
return isSymmtericChild(root.left, root.right); // 2
}
// 2
private boolean isSymmtericChild(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 isSymmtericChild(leftTree.left, rightTree.right)
&& isSymmtericChild(leftTree.right, rightTree.left);
}
}
在线OJ：KY11 二叉树遍历
编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。
输入描述：
输入包括1行字符串，长度不超过100。
输出描述：
可能有多组测试数据，对于每组数据， 输出将输入字符串建立二叉树后中序遍历的序列，每个字符后面都有一个空格。 每个输出结果占一行。
示例:
输入：abc##de#g##f###
输出：c b e g d f a
💯解题思路:
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
static class TreeNode { // 2
public char val;
public TreeNode left;
public TreeNode right;
public TreeNode(char val) {
this.val = val;
}
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
while (in.hasNextLine()) { // 1
String str = in.nextLine();
Main mai = new Main();
TreeNode root = mai.createTree(str); // 3
mai.inOrder(root);
}
}
//构建二叉树
public int i;//遍历字符串的下标 // 4
public TreeNode createTree(String str) { // 3
TreeNode root = null;
if(str.charAt(i) != '#') {
root = new TreeNode(str.charAt(i));
i++;
root.left = createTree(str);
root.right = createTree(str);
}else {
i++;
}
return root;
}
//中序遍历
public void inOrder(TreeNode root) { // 5
if(root == null) {
return;
}
inOrder(root.left);
System.out.print(root.val+" ");
inOrder(root.right);
}
}
在线OJ：102. 二叉树的层序遍历
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]
示例 2：
输入：root = [1]
输出：[[1]]
示例 3：
输入：root = []
输出：[]
提示：
💯解题思路:
实现层序遍历，我们可以设计一个队列来实现, 首先将根节点入队，然后循环每次将队头元素出队(出队时获取到节点中的元素)同时将出队节点的左右孩子结点（不包括空结点）依次入队，以此类推，直到最终队列和当前结点均为空时，表示遍历结束。
看题目中的输出示例, 让我们返回的是一个列表, 列表中的每个元素还是一个列表(存放每一层的数据); 也就是说我们需要将每层的元素分开; 那么这里用顺序表来实现再合适不过, list是要返回的表, tmp表中放一层中的数据, 每次遍历完一层就将tmp添加到list中。
我们可以在每次获取出队元素前，先获取队列中元素个数，这个元素个数就是当前层次的元素个数，这样就能统计每层的数据, 将每层的数据分隔开来。
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> list = new ArrayList<>();
if(root == null) {
return list;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()) {
List<Integer> tmp = new ArrayList<>();
int size = queue.size(); // 1
while(size != 0) {
size--;
TreeNode cur = queue.poll(); // 2
tmp.add(cur.val);
// 3
if(cur.left != null) {
queue.offer(cur.left);
}
if(cur.right != null) {
queue.offer(cur.right);
}
}
list.add(tmp);
}
return list;
}
}
在线OJ：236. 二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
示例 1：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
示例 2：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
示例 3：
输入：root = [1,2], p = 1, q = 2
输出：1
提示：
💯解题思路:
可以利用两个栈分别存储root->p和root->q的二叉树路径，然后将元素多的那一个栈内的元素出栈，直到与另一个栈的元素数量相等，最后两栈同时出栈并比较出栈的元素，如果相等，则相等的那个结点就是p，q的最近公共祖先，最后如果栈为空了还没有找到，p，q在root这棵树上没有公共祖先。
关于 2. 寻找root->p和root->q路径的思路(递归)：
2.1 如果二叉树为空或者目标节点为空，不存在路径。
2.2 创建一个栈，用于存放路径，先假设路径存在并把这条路径上的结点入栈，然后顺着这个路径寻找p或者q，如果没找到，将这条路径上的结点出栈，换另外一条路径寻找。
2.3 函数返回值为boolean，以判断是否找到正确的路径。
对于3和4两点，我们可以分别去左右子树找p，q结点，如果在左右子树均找到，说明4成立，如果在左右子树中只找到一个，就说明3成立，如果在左右子树都没有找到，就说明p，q在root这棵二叉树上没有公共祖先。
class Solution {
//方法二: 递归思路
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null) { // 1
return null;
}
if(root == p || root == q) { // 2
return root;
}
TreeNode leftTree = lowestCommonAncestor(root.left, p, q); // 3 4
TreeNode rightTree = lowestCommonAncestor(root.right, p, q);
if(leftTree != null && rightTree != null) { // 4
return root;
}else if(leftTree != null) { // 3
return leftTree;
}else if(rightTree != null) { // 3
return rightTree;
}else {
return null;
}
}
//方法一: 寻找交点的方法(非递归)
/*public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null || p == null || q == null) {
return null;
}
Stack<TreeNode> stack1 = new Stack<>(); // 1
getPath(root, p, stack1); // 2
Stack<TreeNode> stack2 = new Stack<>(); // 1
getPath(root, q, stack2); // 2
int size1 = stack1.size();
int size2 = stack2.size();
if(size1 > size2) {
int size = size1 - size2;
while(size != 0) { //3
size--;
stack1.pop();
}
}else{
int size = size2- size1;
while(size != 0) {
size--;
stack2.pop();
}
}
while(stack1.peek() != stack2.peek()){ // 4
stack1.pop();
stack2.pop();
}
return stack1.peek();
}
public boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack) {
if(root == null || node == null) { // 2.1
return false;
}
stack.push(root); //2.2
if(root == node) {
return true;
}
//查看左子树路径
boolean flag1 = getPath(root.left, node, stack);
if(flag1) {
return true;
}
//查看右子树路径
boolean flag2 = getPath(root.right, node, stack);
if(flag2) {
return true;
}
//该节点左右子树都没goal结点路径,将这个节点出栈
stack.pop();
return false; // 2.3
}*/
}
在线OJ：JZ36 二叉搜索树与双向链表
描述:
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。如下图所示
数据范围：
输入二叉树的节点数 0 \le n \le 10000≤n≤1000，二叉树中每个节点的值 0\le val \le 10000≤val≤1000
要求：
空间复杂度O(1)O(1)（即在原树上操作），时间复杂度 O(n)O(n)
注意:
1.要求不能创建任何新的结点，只能调整树中结点指针的指向。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继
2.返回链表中的第一个节点的指针
3.函数返回的TreeNode，有左右指针，其实可以看成一个双向链表的数据结构
4.你不用输出双向链表，程序会根据你的返回值自动打印输出
输入描述：
二叉树的根节点
返回值描述：
双向链表的其中一个头节点。
💯解题思路:
将二叉搜索树转换为一个升序排列的循环双向链表，我们知道二叉搜索树进行中序遍历得到的就是一个升序排列的序列, 所以我们可以通过中序遍历二叉树, 进而再修改引用指向, 让节点中left引用指向前驱, right指向后继 ;
public class Solution {
private TreeNode prev; // 1
public TreeNode Convert(TreeNode pRootOfTree) {
if(pRootOfTree == null) {
return null;
}
convertChild(pRootOfTree); // 2
//将指针指向头节点
TreeNode head = pRootOfTree; // 1
while(head.left != null) { // 4
head = head.left;
}
return head;
}
//更改指针指向
public void convertChild(TreeNode cur) { // 2
if(cur == null) {
return;
}
convertChild(cur.left); // 3
cur.left = prev;
if(prev != null) {
prev.right = cur;
}
prev = cur;
convertChild(cur.right);
}
}
在线OJ：105. 从前序与中序遍历序列构造二叉树
给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
示例 1:
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]
示例 2:
输入: preorder = [-1], inorder = [-1]
输出: [-1]
提示:
💯解题思路:
class Solution {
//遍历前序,拿到的是根节点
private int preIndex = 0;
public TreeNode buildTree(int[] preorder, int[] inorder) {
return buildTreeChild(preorder, inorder, 0, inorder.length-1);
}
private TreeNode buildTreeChild(int[] preorder, int[] inorder, int inbegin, int inend) {
if(inbegin > inend) {
return null;
}
//创建根节点
TreeNode root = new TreeNode(preorder[preIndex]); // 1
//找到中序遍历数组中根节点所在位置 // 2
int rootIndex = findIndex(inorder, inbegin, inend, preorder[preIndex]);
preIndex++;
//根,左,右 先创建左树, 再创建右树 // 3
root.left = buildTreeChild(preorder, inorder, inbegin, rootIndex-1);
root.right = buildTreeChild(preorder, inorder, rootIndex+1, inend);
return root;
}
// 2
private int findIndex(int[] inorder, int inbegin, int inend, int val) {
for (int i = inbegin; i <= inend; i++) {
if(inorder[i] == val) {
return i;
}
}
return -1;
}
}
在线OJ：从中序与后序遍历序列构造二叉树
给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
示例 1:
输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出：[3,9,20,null,null,15,7]
示例 2:
输入：inorder = [-1], postorder = [-1]
输出：[-1]
提示:
💯解题思路:
这个与上面一个题的是同一类型的题, 只是将前序遍历变为了后续遍历，而我们知道根据后序遍历去获取根节点应该从后向前依次获取，所以该题只需相较于上面的前序遍历改变后序遍历数组遍历顺序和二叉树创建顺序即可。
class Solution {
//遍历后序,拿到的是根节点
private int postIndex = 0;
public TreeNode buildTree(int[] inorder, int[] postorder) {
postIndex = postorder.length-1;
return buildTreeChild(postorder, inorder, 0, inorder.length-1);
}
private TreeNode buildTreeChild(int[] postorder, int[] inorder, int inbegin, int inend) {
if(inbegin > inend) {
return null;
}
//创建根节点
TreeNode root = new TreeNode(postorder[postIndex]); // 1
//找到中序遍历数组中根节点所在位置 // 2
int rootIndex = findIndex(inorder, inbegin, inend, postorder[postIndex]);
postIndex--;
//左,右,根 先创建右树, 再创建左树 // 3
root.right = buildTreeChild(postorder, inorder, rootIndex+1, inend);
root.left = buildTreeChild(postorder, inorder, inbegin, rootIndex-1);
return root;
}
// 2
private int findIndex(int[] inorder, int inbegin, int inend, int val) {
for (int i = inbegin; i <= inend; i++) {
if(inorder[i] == val) {
return i;
}
}
return -1;
}
}
在线OJ：606. 根据二叉树创建字符串
给你二叉树的根节点 root ，请你采用前序遍历的方式，将二叉树转化为一个由括号和整数组成的字符串，返回构造出的字符串。
空节点使用一对空括号对 “()” 表示，转化后需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。
示例 1：
输入：root = [1,2,3,4]
输出："1(2(4))(3)"
解释：初步转化后得到 "1(2(4)())(3()())" ，但省略所有不必要的空括号对后，字符串应该是"1(2(4))(3)" 。
示例 2：
输入：root = [1,2,3,null,4]
输出："1(2()(4))(3)"
解释：和第一个示例类似，但是无法省略第一个空括号对，否则会破坏输入与输出一一映射的关系。
提示：
💯解题思路:
class Solution {
StringBuilder stringBuilder = new StringBuilder(); // 1
public String tree2str(TreeNode root) {
if(root == null) {
return stringBuilder.toString();
}
stringBuilder.append(root.val); // 2
if(root.left != null) {
stringBuilder.append("(");
tree2str(root.left);
stringBuilder.append(")");
}else {
if(root.right == null) {
return stringBuilder.toString();
}else {
stringBuilder.append("()");
}
}
if(root.right != null) { // 3
stringBuilder.append("(");
tree2str(root.right);
stringBuilder.append(")");
}
return stringBuilder.toString();
}
}
在线OJ：144. 二叉树的前序遍历
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
示例 1：
输入：root = [1,null,2,3]
输出：[1,2,3]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]
示例 4：
输入：root = [1,2]
输出：[1,2]
示例 5：
输入：root = [1,null,2]
输出：[1,2]
提示：
进阶：递归算法很简单，你可以通过迭代算法完成吗？
💯解题思路:
class Solution {
//方法三:利用栈非递归实现
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while(cur != null || !stack.isEmpty()) {
while (cur != null) {
stack.push(cur);
list.add(cur.val);
cur = cur.left;
}
TreeNode top = stack.pop();
cur = top.right;
}
return list;
}
//方法一
/*List<Integer> list = new ArrayList<>();
public List<Integer> preorderTraversal(TreeNode root) {
if(root == null) {
return list;
}
list.add(root.val);
preorderTraversal(root.left);
preorderTraversal(root.right);
return list;
}*/
//方法二
/*public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if(root == null) {
return list;
}
list.add(root.val);
List<Integer> leftTree = preorderTraversal(root.left);
list.addAll(leftTree);
List<Integer> rightTree = preorderTraversal(root.right);
list.addAll(rightTree);
return list;
}*/
}
在线OJ：94. 二叉树的中序遍历
给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
示例 1：
输入：root = [1,null,2,3]
输出：[1,3,2]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]
提示：
树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
💯解题思路:
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>(); // 1
TreeNode cur = root;
while(cur != null || !stack.isEmpty()) {
while (cur != null) {
stack.push(cur); // 2
cur = cur.left;
}
TreeNode top = stack.pop();
list.add(top.val); // 3
cur = top.right;
}
return list;
}
}
在线OJ：145. 二叉树的后序遍历
给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。
示例 1：
输入：root = [1,null,2,3]
输出：[3,2,1]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]
提示：
树中节点的数目在范围 [0, 100] 内
-100 <= Node.val <= 100
进阶：递归算法很简单，你可以通过迭代算法完成吗？
💯解题思路:
我们应该知道前, 中, 后序遍历在遍历时的搜索顺序其实是相同的, 区别在于访问结点数据的时机不同, 再对比上面的前,中序两道题, 上面的两道题在遍右树时, 左树和根中的数据已经访问过了, 所以在更新当前遍历结点为栈顶元素右结点时, 栈顶元素可以直接出栈; 但在后序遍历中更新为右结点时, 根节点中的元素还没有被访问, 此时是不能出栈的; 要在访问了根结点数据之后再出栈;
同样的, 按照上面两题的遍历思路, 只是更改访问结点数据时机可不可行呢, 按照此时的思路代码如下:
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
TreeNode flag = null;
while(cur != null || !stack.isEmpty()) {
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
TreeNode top = stack.peek();
if(top.right == null) {
list.add(top.val);
stack.pop();
}else{
cur = top.right;
}
}
return list;
}
}
其实上面的代码是有一些问题的, 看这几行代码,
这里的代码, 当结点的右子树不为空的时候, 我们再去遍历右子树, 这里就有问题了, 当遍历完一个结点的右子树后返回, 由于结点没有出栈, top又重新指向了原来的结点, 此时再去遍历top的右树就重复遍历了, 造成了死循环,
为了解决这个问题，我们可以用一个标记来提前记录遍历完后的右子树的根结点, 记为flag; 有了flag, 当我们遍历完右子树, top结点又回到这棵右子树的根结点, ，如果此时该结点的右子树为空或者flag与该结点右子树的根结点相同，就表示右子树已经遍历完成了，不需要再次遍历了, 就将这个结点出栈并保存结点中的数据, 并将出栈结点用flag记录(表示这棵树已经遍历完了),
所以重新整理思路如下:
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>(); // 1
TreeNode cur = root;
TreeNode flag = null; // 1
while(cur != null || !stack.isEmpty()) {
while (cur != null) {
stack.push(cur); // 2
cur = cur.left;
}
TreeNode top = stack.peek();
if(top.right == null || top.right == flag) {
list.add(top.val); // 3
flag = stack.pop();
}else{
cur = top.right;
}
}
return list;
}
}
对于具有离线功能的智能手机应用程序，我正在为Xml文件创建单向文本同步。我希望我的服务器将增量/差异(例如GNU差异补丁)发送到目标设备。这是计划:Time=0Server:hasversion_1ofXmlfile(~800kiB)Client:hasversion_1ofXmlfile(~800kiB)Time=1Server:hasversion_1andversion_2ofXmlfile(each~800kiB)computesdeltaoftheseversions(=patch)(~10kiB)sendspatchtoClient(~10kiBtransferred)Cl
我构建了两个需要相互通信和发送文件的Rails应用程序。例如，一个Rails应用程序会发送请求以查看其他应用程序数据库中的表。然后另一个应用程序将呈现该表的json并将其发回。我还希望一个应用程序将存储在其公共(public)目录中的文本文件发送到另一个应用程序的公共(public)目录。我从来没有做过这样的事情，所以我什至不知道从哪里开始。任何帮助，将不胜感激。谢谢! 最佳答案 无论Rails是什么，几乎所有Web应用程序都有您的要求，大多数现代Web应用程序都需要相互通信。但是有一个小小的理解需要你坚持下去，网站不应直接访问彼此
我尝试运行2.x应用程序。我使用rvm并为此应用程序设置其他版本的ruby:$rvmuseree-1.8.7-head我尝试运行服务器，然后出现很多错误:$script/serverNOTE:Gem.source_indexisdeprecated,useSpecification.Itwillberemovedonorafter2011-11-01.Gem.source_indexcalledfrom/Users/serg/rails_projects_terminal/work_proj/spohelp/config/../vendor/rails/railties/lib/r
刚入门rails，开始慢慢理解。有人可以解释或给我一些关于在application_controller中编码的好处或时间和原因的想法吗？有哪些用例。您如何为Rails应用程序使用应用程序Controller？我不想在那里放太多代码，因为据我了解，每个请求都会调用此Controller。这是真的？ 最佳答案 ApplicationController实际上是您应用程序中的每个其他Controller都将从中继承的类(尽管这不是强制性的)。我同意不要用太多代码弄乱它并保持干净整洁的态度，尽管在某些情况下ApplicationContr
我是一个Rails初学者，但我想从我的RailsView(html.haml文件)中查看Ruby变量的内容。我试图在ruby中打印出变量(认为它会在终端中出现)，但没有得到任何结果。有什么建议吗？我知道Rails调试器，但更喜欢使用inspect来打印我的变量。 最佳答案 您可以在View中使用puts方法将信息输出到服务器控制台。您应该能够在View中的任何位置使用Haml执行以下操作:-puts@my_variable.inspect 关于ruby-on-rails-如何在我的R
是否可以在应用程序中包含的gem代码中知道应用程序的Rails文件系统根目录？这是gem来源的示例:moduleMyGemdefself.included(base)putsRails.root#returnnilendendActionController::Base.send:include,MyGem谢谢，抱歉我的英语不好 最佳答案 我发现解决类似问题的解决方案是使用railtie初始化程序包含我的模块。所以，在你的/lib/mygem/railtie.rbmoduleMyGemclassRailtie使用此代码，您的模块将在
无论您是想搭建桌面端、WEB端或者移动端APP应用，HOOPSPlatform组件都可以为您提供弹性的3D集成架构，同时，由工业领域3D技术专家组成的HOOPS技术团队也能为您提供技术支持服务。如果您的客户期望有一种在多个平台（桌面/WEB/APP，而且某些客户端是“瘦”客户端）快速、方便地将数据接入到3D应用系统的解决方案，并且当访问数据时，在各个平台上的性能和用户体验保持一致，HOOPSPlatform将帮助您完成。利用HOOPSPlatform，您可以开发在任何环境下的3D基础应用架构。HOOPSPlatform可以帮您打造3D创新型产品，HOOPSSDK包含的技术有：快速且准确的CAD
导读：随着叮咚买菜业务的发展，不同的业务场景对数据分析提出了不同的需求，他们希望引入一款实时OLAP数据库，构建一个灵活的多维实时查询和分析的平台，统一数据的接入和查询方案，解决各业务线对数据高效实时查询和精细化运营的需求。经过调研选型，最终引入ApacheDoris作为最终的OLAP分析引擎，Doris作为核心的OLAP引擎支持复杂地分析操作、提供多维的数据视图，在叮咚买菜数十个业务场景中广泛应用。作者｜叮咚买菜资深数据工程师韩青叮咚买菜创立于2017年5月，是一家专注美好食物的创业公司。叮咚买菜专注吃的事业，为满足更多人“想吃什么”而努力，通过美好食材的供应、美好滋味的开发以及美食品牌的孵
在应用开发中，有时候我们需要获取系统的设备信息，用于数据上报和行为分析。那在鸿蒙系统中，我们应该怎么去获取设备的系统信息呢，比如说获取手机的系统版本号、手机的制造商、手机型号等数据。1、获取方式这里分为两种情况，一种是设备信息的获取，一种是系统信息的获取。1.1、获取设备信息获取设备信息，鸿蒙的SDK包为我们提供了DeviceInfo类，通过该类的一些静态方法，可以获取设备信息，DeviceInfo类的包路径为：ohos.system.DeviceInfo.具体的方法如下：ModifierandTypeMethodDescriptionstatic StringgetAbiList()Obt
我们目前正在为ROR3.2开发自定义cms引擎。在这个过程中，我们希望成为我们的rails应用程序中的一等公民的几个类类型起源，这意味着它们应该驻留在应用程序的app文件夹下，它是插件。目前我们有以下类型:数据源数据类型查看我在app文件夹下创建了多个目录来保存这些:应用/数据源应用/数据类型应用/View更多类型将随之而来，我有点担心应用程序文件夹被这么多目录污染。因此，我想将它们移动到一个子目录/模块中，该子目录/模块包含cms定义的所有类型。所有类都应位于MyCms命名空间内，目录布局应如下所示:应用程序/my_cms/data_source应用程序/my_cms/data_ty