文章目录
- 判断是否是完全二叉树
- 找出p和q的最近的公共祖先
- 非递归实现前序遍历
- 非递归实现中序遍历
- 非递归实现后序遍历
判断是否是完全二叉树
boolean isCompleteTree(TreeNode root){
if (root == null){
return true;
}
//创建队列
Queue<TreeNode> queue = new LinkedList<>();
//把根放进队列里
queue.offer(root);
while (!queue.isEmpty()){
//把出队列的放进cur里
TreeNode cur = queue.poll();
//当cur不等于空时，把cur的左子树和右子树放进队列
if (cur != null){
queue.offer(cur.left);
queue.offer(cur.right);
}else{
//如果cur放进了null，说明要跳出队列进入判断环节
break;
}
}
while(!queue.isEmpty()){
TreeNode tmp = queue.peek();//瞄一眼队列的数
if (tmp == null){
queue.poll();
}else{
//遇到不为空的说明不是完全二叉树
return false;
}
}
//来到这里说明tmp全部是空的,是完全二叉树
return true;
}
找出p和q的最近的公共祖先
1.root节点是p或q其中的一个，那么root就是最近的公共祖先
2.p和q分别在root的两侧，那么root是最近的公共祖先
3.p和q在root的同一侧
原理：root还是在遍历这棵树，遇到p或q就返回。
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) return null;
if (root == p || root == q) {
return root;
}
TreeNode leftTree = lowestCommonAncestor(root.left, p, q);
TreeNode rightTree = lowestCommonAncestor(root.left, p, q);
if (leftTree != null && rightTree != null) {
return root;
} else if (leftTree != null) {
return leftTree;
} else {
return rightTree;
}
}
还有第二种方法
大概意思就是：找p那条路径，和q那条路径出现的节点，然后放进两个栈里，保证两个栈的数相同，多的去掉，然后栈中相同的元素就是他们最近的公共祖先。
public class BinaryTree {
static class TreeNode{
public char val;
public TreeNode left;
public TreeNode right;
public TreeNode(char val) {
this.val = val;
}
}
public TreeNode creatTree(){
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;
return A;
}
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 = stackP.size();
if (sizeP > sizeQ){
int size = sizeP - sizeQ;
while (size != 0){
stackP.pop();
size--;
}
}else {
int size = sizeQ - sizeP;
while (size != 0){
stackQ.pop();
size--;
}
}
//两个栈元素一样多
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){
if (root == null || node == null){
return false;
}
stack.push(root);
if (root == node){
return true;
}
boolean flg1 = getPath(root.left, node, stack);
if(flg1){
return true;
}
boolean flg2 = getPath(root.right, node, stack);
if(flg2){
return true;
}
stack.pop();
return false;
}
}
非递归实现前序遍历
//递归实现前序遍历
void preOrder(TreeNode root){
//根左右
if(root == null){
return;
}
System.out.print(root.val+" ");
preOrder(root.left);
preOrder(root.right);
}
//非递归实现前序遍历
void preOrderNor(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);
System.out.print(cur.val + " ");
cur = cur.left;
}
TreeNode top = stack.pop();
cur = top.right;
//1.为空，返回；不为空创建栈，让cur=root;
//当cur!=null时，把cur放进栈里，并打印cur.val；再让cur=root.left。
//当cur==null时，让top=栈顶元素,然后让cur=top.right
}
}
非递归实现中序遍历
//中序遍历
void inOrder(TreeNode root){
//左根右
if(root == null){
return;
}
inOrder(root.left);
System.out.print(root.val+" ");
inOrder(root.right);
}
//非递归中序遍历
void inorderNor(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;
}
//不为空，创建栈，让cur=root,把cur放进栈里，然后遍历cur的左边。
//直到cur遇到空，说明cur的左边遍历完了
//让top=栈顶元素，并打印top的值，让cur=top.right。
}
非递归实现后序遍历
//后序遍历
void postOrder(TreeNode root){
//左右根
if(root == null){
return;
}
postOrder(root.left);
postOrder(root.right);
System.out.print(root.val+" ");
}
//非递归后序遍历
void postOrderNor(TreeNode root){
if (root == null){
return;
}
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
TreeNode prev = null;
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;
}
//先创建栈，让cur=root，cur不等于空或者栈不为空，当cur不等于空时，让cur入栈,然后让cur=cur.left，
//直到当cur等于空时,定义prev=null；让top=瞄一眼栈顶元素，如果等于空或者top.right=prev进入循环，
// 循环内打印top.val，并且出栈，然后让prev=top，否则让cur=cur.right
}
![算法专题[递归-搜索-回溯-2-DFS]](https://img-blog.csdnimg.cn/direct/498028909294467ab4c0a44389565e35.png)
