采用二叉树的先序遍历，在叶子结点判断数字和是否相等即可，需要注意的是测试数据里，如果根结点的值等于数字和，是不算一条路径的，所以需要进行排除；而且题目只要求找到一条路径，所以可以假如左子树已经找到路径，那么右子树就不需要找了，可以进行剪枝。 时间复杂度最慢O(N)，平均复杂度小于O(N) 空间复杂度O(1) import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * } */ public clas...

因为题目说了字符串只有字母类型，那么可以使用2个数组，26个字母大小写一共需要52个位来存字母出现的次数，另一个数组存字母出现的位置，循环一遍将出现的次数和位置都存进数组里，最后遍历一遍字母出现次数的数字，只要次数是1就更新res位置，最后得到的就是位置最前的。 时间复杂度O(N)，空间复杂度O(52*2)--->O(1) import java.util.*; public class Solution { public int FirstNotRepeatingChar(String str) { int[] alph = new int[52]; ...

为了达到平衡树的特点：左右子树高度差不能超过1，也就是说左右子树的结点数量基本上一致（相差<1），那么就可以使用二分法的思想，将升序数组的中位数找到，然后分出左右2个区间分别作为左右子树，如此反复直到区间数为0即可。 因为需要遍历所有结点，所以时间复杂度O(N)，空间复杂度O(N)。 import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * } */ public class Solutio...

双栈解法 题目要求按照之字形输出结果， 但是在二叉树里，层序遍历用的是队列，而且是固定从左到右输出； 而前中后序都不满足题目要求，观察发现，之字形和层序遍历的区别， 在于：层序队列用的队列来存结点，先存什么就先出什么，而之字形要求顺序反过来，这里自然地想到了栈，先进后出。 继续观察发现，发现后续结点的遍历，需要根据遍历的方向，来决定先存左孩子还是右孩子，假如当前是从右往左遍历，那么需要先存右孩子，再存左孩子；反之需要先存左孩子再存右孩子。 思路：分成两个栈：从左往右遍历的栈，和从右向左遍历的栈；或者可以理解成先存左右孩子的哪个节点的栈。声明好两个栈之后，就是只要两个栈都不为空，说明有树还没遍历...

后续遍历大法 因为，该节点要找到最近公共祖先，所以需要先确定两个要找结点的位置，找到之后再找祖先，那么这里就自然可以想到二叉树的后序遍历，最后得到的就是最近的公共祖先。 思路：后序遍历 1.如果当前结点就是要找的结点，那么把当前结点值返回； 2.如果当前结点不是要找的结点，那么返回-1； 3.如果当前结点的左子树和右子树中，有一个返回的值不是-1，说明他们之中找到了一个结点，那么此时就要判断当前结点的值是不是要找的值，如果是，说明当前结点就是最近公共祖先，直接返回当前结点值；否则继续向上回退找祖先。 4.以上的时间复杂度是O(N)，空间复杂度O(N) import java.util.*; ...