题目:
最近公共祖先的意思就是,找到他们俩个指定结点的相交结点
我们分为这四种情况:
1. root就是q/p的其中一个,那么root就是最近公共祖先
2. 如果p和q分布在root俩侧 那么root就是最近公共祖先
3. 如果p和q在同一侧, root先碰到谁,谁就是最近公共祖先
4. 在3的基础上如果p,q在同一层,那么root就是最近公共祖先
此时这里后面有一部分代码是可以这么合并
我们还有另外一种写法,也就是之前求链表的时候,链表分叉了我们找到分叉的交点.
我们使用俩个栈来保存经过p,q的路径上的结点,然后我们计算俩个栈的大小,让大的那个栈先出多余的元素,当俩个栈的大小一致的时候,我们就同时出栈,直到出来的俩个元素相等为止.(该方法多练,不太熟)
1> 获取p,q的路径栈
2> 出栈多的元素
3> 同时出栈元素,直到出栈的元素一样
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q){
//如果root是空,那么就没有公共结点,返回Null
if(root == null) {
return null;
}
//如果root就是p,q中的一个,返回root
if(p == root || q == root) {
return root;
}
//获取左右子树
TreeNode leftTree = lowestCommonAncestor(root.left,p,q);
TreeNode rightTree = lowestCommonAncestor(root.right,p,q);
//如果左右子树都不为空,说明p,q分别分布在左右子树上
if(leftTree != null && rightTree != null) {
return root;
}
//左子树为空,那么都在右子树上
if(leftTree == null && rightTree != null) {
return rightTree;
}
//右子树为空,那么都在左子树上
if(leftTree != null && rightTree == null){
return leftTree;
}
return null;
}法2的具体代码:
public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
if(root == null) {
return null;
}
Stack<TreeNode> stackP = new Stack<>();
Stack<TreeNode> stackQ = new Stack<>();
//我们往栈里面放左右子树的路径元素
getPath(root,p,stackP);
getPath(root,q,stackQ);
//计算栈的大小
int sizeP = stackP.size();
int sizeQ = stackQ.size();
int redundent = Math.abs(sizeP-sizeQ);
//弹出多出来的元素
if(sizeP > sizeQ) {
while (redundent != 0) {
redundent--;
stackP.pop();
}
}else if(sizeP < sizeQ) {
while (redundent != 0) {
redundent--;
stackQ.pop();
}
}
//此时俩个栈的元素个数是一样的
while (!stackP.isEmpty() && !stackQ.isEmpty()){
if(stackP.peek() == stackQ.peek()) {
//如果俩者元素一样就返回该结点
return stackP.peek();
}else {
//如果不一样就出栈
stackP.pop();
stackQ.pop();
}
}
return null;
}
private boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack) { //node代表p或者q,如果是路径上的结点就放进栈里面去
//如果是空的话
if (root == null || node == null) {
return false;
}
//不为空就把根结点放入
stack.push(root);
//如果root等于p或q
if (root == node) {
return true;
}
//我们判断左右子树
boolean flg1 = getPath(root.left,node,stack);
if (flg1 == true) {
return true;
}
boolean flag2 = getPath(root.right,node,stack);
if(flag2 == true) {
return true;
}
//此时左右子树都为空,我们就把root结点弹出,它就不属于我们的路径
stack.pop();
return false;
}(多自己写几次)
public int preIndex;
public TreeNode buildTree(int[] preorder,int[] inorder) {
return buildTreeChilde(preorder,inorder,0,inorder.length-1);
}
private TreeNode buildTreeChilde(int[] preorder,int[] inorder,int inbegin,int inend) {
//TODO 给的是前序遍历的结果,我们用前序遍历的方式来创建即可
if(inbegin > inend) {
return null;//没有左树或者没有右树
}
//先创建根结点
TreeNode root = new TreeNode(preorder[preIndex]);
// preIndex++;放在这里就会影响下面找根的操作
//找到根结点在中序遍历的位置
int roorIndex = findIndexRoot(inorder,inbegin,inend,preorder[preIndex]);
//判断下标是否合法
if(roorIndex == -1) {
return null;
}
preIndex++;
//再创建左子树
root.left = buildTreeChilde(preorder,inorder,inbegin,roorIndex - 1);
//创建右子树
root.right = buildTreeChilde(preorder,inorder,roorIndex + 1,inend);
//左右走完就返回根即可
return root;
}
//在区间范围找到一个值
private int findIndexRoot(int[] inorder,int inbegin,int inend,int key) {
for (int i = inbegin ;i <= inend; i++) {//此刻为等号是因为上面传参传进来的是inorder.length-1
if(inorder[i] == key) {
return i;
}
}
return -1;
}(多自己写几次)
class Solution {
public int postIndex;
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]);
//找到中序遍历里面的根结点的位置
int rootIndex = findRootIndex(inorder,inbegin,inend,postorder[postIndex]);
//判断rootIndex是否合法
if(rootIndex == -1) {
return null;
}
postIndex--;
//创建右树
root.right = buildTreeChild(postorder,inorder,rootIndex+1,inend);
//创建左子树
root.left = buildTreeChild(postorder,inorder,inbegin,rootIndex-1);
return root;
}
private int findRootIndex(int[] inorder, int inbegin,int inend,int key) {
for (int i = inbegin; i <= inend ; i++) {
if(inorder[i] == key) {
//返回找到的中序遍历的根结点的下标
return i;
}
}
//如果找不到就返回-1
return -1;
}
}题目:
首先我们拼接字符串用的是StringBuilder,然后StringBuilder转字符串我们用的是stringBuilder.toString()
我们先把根结点加入StringBuilder,然后我们分析左子树,先拼接"(",然后继续递归左子树,直到到底(左右都为空)为止,然后返回回来,我们再拼接")",如果在这个过程中我们如果遇到左子树为空右子树不为空的情况就拼接"()",同样右子树也是如此.
(多写几遍)
public String tree2str(TreeNode root) {
//创建StringBuilder
StringBuilder stringBuilder = new StringBuilder();
//进行拼接
treeChild(root,stringBuilder);
return stringBuilder.toString();
}
private void treeChild(TreeNode root,StringBuilder stringBuilder){
//如果根结点不是空,我们就把它加入进来
if(root == null) {
return;
}
//先拼接根结点
stringBuilder.append(root.val);
//先搞左边
if(root.left != null) {
//我们先加入"("
stringBuilder.append("(");
//进行递归
treeChild(root.left,stringBuilder);
//递归完了就把括号加入)
stringBuilder.append(")");
}else {
//此时左边为空
if(root.right == null) {
return;
}else {
//如果左边为空,右边不为空,那么就凭借()代表左边是空的
//只有左边为空右边不为空的时候我们才加()
stringBuilder.append("()");
}
}
//再搞右边
if(root.right != null) {
//我们先加入"("
stringBuilder.append("(");
//进行递归
treeChild(root.right,stringBuilder);
stringBuilder.append(")");
}else {
return;
}
}这里有一个点,第一层循环的条件我们加上了栈不为空这个条件,如果cur当前是D此时我们再一次循环就无法继续进入循环去进行右子树的操作了.
void preOderNor1(TreeNode root) {
if(root == null) {
return;
}
//创建栈和cur
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
//入栈
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;
}
}我们的栈里面保存的就是每棵子树的根结点,我们出栈一个元素,就可以通过它知道它的右子树的情况.
//中序遍历:
void inorderNor1(TreeNode root) {
if(root == null) {
return;
}
//创建栈
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
//一直往左边走
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;
}
} //TODO 二叉树的后序非递归遍历
void postOrderNor(TreeNode root) {
if(root == null) {
return;
}
Stack<TreeNode> stack = new Stack<>();
TreeNode prev = null;//避免死循环
TreeNode cur = root;
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记录的是被打印了的结点
prev = top;
} else {
//如果右边不为空,那么就要进入栈
cur = top.right;
}
}
}