数据结构（Java）：力扣二叉树面试OJ题（二）【进阶】

💎 1、题一：二叉树的层序遍历

🌟 1.1 思路1（递归求解）

🌟 1.1.1 思路1代码

🔆 1.2 思路2（队列求解）

🔆 1.2.1 思路2代码

💎 2、题二：判断是否为完全二叉树

🌟 2.1 思路分析

🌟 2.2 代码

💎 3、题三：求二叉树中节点的最近公共祖先

🌟 3.1 思路分析

🌟 3.2 代码

💎 4、题四：根据二叉树创建字符串

🌟 4.1 思路分析

🌟 4.2 代码

💎 5、题五：二叉树前序遍历递归实现与非递归实现

🌟 5.1 递归实现->思路分析

🌟 5.1.1 递归实现->代码

🔆 5.2 非递归实现->思路分析

编辑 🔆 5.2.1 非递归实现->代码

💎 6、题六：二叉树中序遍历递归实现与非递归实现

🌟 6.1 递归实现->代码

🔆 6.2 非递归实现->代码

💎 7、题七：二叉树后序遍历递归实现与非递归实现

🌟 7.1 递归实现->代码

🔆 7.2 非递归实现->思路分析

🔆 7.2.1 非递归实现->代码

💎 1、题一：二叉树的层序遍历

. - 力扣（LeetCode）

层序遍历，即从上到下，从左到右，一层一层的将数据遍历一遍。

🌟 1.1 思路1（递归求解）

首先，根据上篇求树高度的方法，求出二叉树的高度。接着，实例化出高度个一维顺序表添加到二维顺序表中。
记录好每层数据的层数，根据层数并按顺序来将来将数据添加到二维顺序表的第几行中（记录层数来放入数据，是解题关键点！！！）。
默认根节点是第0层，与顺序表下标相对应。
这里以前序遍历的思想递归，添加各层数据。

🌟 1.1.1 思路1代码

class Solution {public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> listVal = new ArrayList<>();if(root == null) {//注意：若根节点为空，要返回空的顺序表return listVal;};int height = treeHeight(root);for(int i = 0; i < height; i++) {List<Integer> list = new ArrayList<>();listVal.add(list);}//根节点的层数默认为0addNode(root,0,listVal);return listVal;}//求树高度public int treeHeight(TreeNode root) {if(root == null) return 0;return Math.max(treeHeight(root.left),treeHeight(root.right)) + 1;}public void addNode(TreeNode root,int level,List<List<Integer>> listVal) {if(root == null) {return;}//以前序遍历的思想，根据层数来将数据添加到该行的顺序表中listVal.get(level).add(root.val);addNode(root.left,level+1,listVal);addNode(root.right,level+1,listVal);} 
}

🔆 1.2 思路2（队列求解）

首先创建一个队列，将根节点放入队列当中
每次循环前记录队列中元素个数size，依次出队size个元素，每次出队的元素（节点）都要判断其左右子树是否为空，若不为空则添加到队列中
将每次出队的元素的val值添加到一维顺序表中，size个元素全部出队完后，将这个一维顺序表添加到二维顺序表中，也就是说，每size个出队的元素都是同一层的节点
循环以上过程，直至元素全部添加至二维顺序表中（队列为空）

🔆 1.2.1 思路2代码

class Solution {public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> listVal = new ArrayList<>();if (root == null) {//注意：若根节点为空，要返回空的顺序表return listVal; }Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);//队列空时，说明节点已全部添加到二维顺序表中while (!queue.isEmpty()) {int size = queue.size();//存储每一层节点的顺序表List<Integer> list = new ArrayList<>();//将队列中的size个元素依次出队，//并判断其左右子树是否为空，若不为空则添加到队列中while (size != 0) {TreeNode out = queue.poll();list.add(out.val);if (out.left != null) {queue.offer(out.left);}if (out.right != null) {queue.offer(out.right);}size--;}//将每一层的一维顺序表添加到二维顺序表中listVal.add(list);}return listVal;}
}

💎 2、题二：判断是否为完全二叉树

本题无链接，

题目即：给出一棵树的根节点，判断是否为完全二叉树。

🌟 2.1 思路分析

这题的解题思路和上一题队列求解差不多，都是借助队列这一数据结构：

首先，创建队列，放入根节点。
将一个元素出队，cur接收出队元素，判断cur是否为空，若cur不为空，则将其左右孩子放入队列中（若左右子树为null，也要将null入队），循环这一过程。
当cur为null时结束循环（出队的是null，cur接收，此时cur为null），此时，只要判断队列中的剩余元素是否存在非null元素：若剩余元素全为null则说明该树为完全二叉树；若剩余元素存在非null元素则说明该树不为完全二叉树。

🌟 2.2 代码

boolean isCompleteTree(TreeNode root) {if(root == null) {return true;}//创建队列 添加根节点Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);//当cur不为空时，添加其左右孩子TreeNode cur = root;while (cur != null) {cur = queue.poll();if (cur != null) {queue.offer(cur.left);queue.offer(cur.right);}}//cur为空时，判断队列中是否有非空元素//若剩余元素全为null则说明该树为完全二叉树；// 若剩余元素存在非null元素则说明该树不为完全二叉树。boolean flg = false;while (!queue.isEmpty()) {TreeNode cur2 = queue.poll();if (cur2 != null) {flg = true;}}if (flg == true) {return false;}else {return true;}}

💎 3、题三：求二叉树中节点的最近公共祖先

. - 力扣（LeetCode）

🌟 3.1 思路分析

①：当p、q在根节点的左右子树上时，祖先就是这个根节点
②：当p、q都在根节点的右子树上时，由于节点的祖先可以是它自己，所以祖先就是p或q本身
③：当p、q都在根节点的左子树上时，由于节点的祖先可以是它自己，所以祖先就是p或q本身
以前序遍历思想递归，若遇见p、q节点便返回
若左右子树都有返回值，说明祖先就是这个根节点；（对于第一层的根节点）若只有左子树有返回值，说明p、q均在左子树上，返回的节点就是最近祖先；（对于第一层的根节点）若只有右子树有返回值，说明p、q均在右子树上，返回的节点就是最近祖先。

🌟 3.2 代码

class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {return findNode( root,  p,  q);}public TreeNode findNode(TreeNode root, TreeNode p, TreeNode q) {if(root == null) {return null;}//先判断根节点是否为p、q节点if(root.val == p.val || root.val == q.val) {return root;}//查找左右子树TreeNode leftNode = findNode(root.left,p,q);TreeNode rightNode = findNode(root.right,p,q);   //若左右子树都有返回值，说明祖先就是这个根节点    if(leftNode != null && rightNode != null) {return root;}//在左树上找到了if(leftNode != null && rightNode == null) {return leftNode;}//在右树上找到了if(rightNode != null && leftNode == null) {return rightNode;}return null;}
}

💎 4、题四：根据二叉树创建字符串

. - 力扣（LeetCode）

🌟 4.1 思路分析

借助StringBuffer拼接字符串，最后返回字符串
以前序遍历思想递归
拼接当前根节点，判断根节点的左孩子是否为空，若左孩子不为空则拼接"("，并递归左子树；若左孩子为空且右孩子为空，则直接返回即可；若左孩子为空但右孩子不为空，注意！！！此时应该拼接"()"，继续递归右子树。
若右孩子为空，则直接返回；若右孩子不为空，则拼接"("并递归右子树。
在根节点的左右子树完成即递归回退后拼接相应的")"
调用toString方法返回字符串

🌟 4.2 代码

 class Solution {StringBuilder stringBuilder = new StringBuilder();public String tree2str(TreeNode root) {tree2strChild(root);return stringBuilder.toString();}public void tree2strChild(TreeNode root) {if(root == null) {return ;}stringBuilder.append(root.val);if(root.left != null) {//左子树不为空，则必然添加"("stringBuilder.append("(");//递归左子树tree2strChild(root.left);//该节点左子树完，则拼接")"stringBuilder.append(")");}else {//左子树为空，且右子树为空，直接返回if(root.right == null) {return;}else {//左子树为空，但右子树不为空，需拼接"()"stringBuilder.append("()");}}//若右孩子为空，则直接返回；若右孩子不为空，则拼接"("并递归右子树if (root.right != null) {stringBuilder.append("(");tree2str(root.right);stringBuilder.append(")");}else {return;}}
}

💎 5、题五：二叉树前序遍历递归实现与非递归实现

. - 力扣（LeetCode）

🌟 5.1 递归实现->思路分析

递归实现前序遍历的思想很简单：就是先将根节点的数据放入顺序表中，再将左子树的数据放入顺序表中，再将右子树的数据放入顺序表中。

🌟 5.1.1 递归实现->代码

class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> list = new ArrayList<>();if(root == null) {return list;}list.add(root.val);List<Integer> leftList = preorderTraversal(root.left);list.addAll(leftList);List<Integer> rightList = preorderTraversal(root.right);list.addAll(rightList);return list;}
}

🔆 5.2 非递归实现->思路分析

非递归实现遍历，我们需要借助一种数据结构--->栈

注意：本题要求将数值放入顺序表中，返回顺序表。故这里访问根节点时，对根节点的操作是将根节点的val值添加到顺序表中。

创建栈和顺序表，将根节点赋值给cur
将cur入栈并将cur的val值添加到顺序表中，cur更新为cur的left，接着将cur入栈并将cur的val值添加到顺序表中。循环操作，直到cur为空
此时cur为空，pop弹出栈顶元素赋给top，将cur更新为top.right；若top.right为空，即更新的cur为空，则继续弹出栈顶元素（top接收），直至cur不为空。
此时cur不为空，循环2、3步骤，直至栈中元素为空，说明树中元素已按照前序遍历的方式全部添加到了顺序表中。

🔆 5.2.1 非递归实现->代码

class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> list = new ArrayList<>();Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;//注意这里的循环条件//因为后续cur为空时要弹出栈顶元素，故栈不能为空//且一开始时栈为空，故cur不为空就可进入循环//当栈空且cur为空，说明前序遍历已完成while (cur != null || !stack.isEmpty()) {//cur不为空就要进栈，并添加进顺序表//cur = cur.leftwhile (cur != null) {stack.push(cur);list.add(cur.val);cur = cur.left;}//当cur为空时，弹出栈顶元素（top），赋给cur其右子树//若cur还是为空（top.right为空），循环过来继续弹出元素，并赋给cur新的top.rightTreeNode top = stack.pop();cur = top.right;}return list;}
}

💎 6、题六：二叉树中序遍历递归实现与非递归实现

. - 力扣（LeetCode）

中序遍历的实现，不管是在递归实现上还是在非递归实现上，和前序遍历的思想都是相同的，只是访问根节点的时机有所不同。

🌟 6.1 递归实现->代码

class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> list = new ArrayList<>(); if(root == null) {return list;}List<Integer> listLeft = inorderTraversal(root.left);list.addAll(listLeft);list.add(root.val);List<Integer> listRight = inorderTraversal(root.right);list.addAll(listRight);return list;}
}

🔆 6.2 非递归实现->代码

class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> list = new ArrayList<>();Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;//注意这里的循环条件//因为后续cur为空时要弹出栈顶元素，故栈不能为空//且一开始时栈为空，故cur不为空就可进入循环//当栈空且cur为空，说明前序遍历已完成while (cur != null || !stack.isEmpty()) {//cur走左子树while (cur != null) {stack.push(cur);cur = cur.left;}//当cur为空时，弹出栈顶元素（top），添加进顺序表，赋给cur其右子树//若cur还是为空（top.right为空），循环过来继续弹出元素，并赋给cur新的top.rightTreeNode top = stack.pop();list.add(top.val);cur = top.right;}return list;}
}

💎 7、题七：二叉树后序遍历递归实现与非递归实现

. - 力扣（LeetCode）

后序遍历的实现，在递归上，与前序、中序遍历的思想是相同的，在此不再赘述。

而在非递归的实现上，后序遍历需要额外注意几点。

🌟 7.1 递归实现->代码

class Solution {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> list = new ArrayList<>();if(root == null) {return list;}List<Integer> list1 = postorderTraversal(root.left);list.addAll(list1);List<Integer> list2 = postorderTraversal(root.right);list.addAll(list2);list.add(root.val);return list;}
}

🔆 7.2 非递归实现->思路分析

后序遍历在非递归的实现上，需要额外注意几点：

当cur为空时，不可直接将栈顶元素弹出并添加进顺序表（或打印，只是访问根节点时的操作不同）
因为栈顶元素即根节点，后序遍历，需要判断栈顶元素的右孩子是否为空，若为空，才可弹出栈顶元素并打印；若右孩子不为空，需要先对右子树中的元素进行入栈和打印操作
而当栈顶元素的右孩子不为空时，我们又需要额外注意一点！！！当栈顶元素的右孩子不为空时，那就说明这个栈顶元素将永远不能出栈，会造成死循环！！！我们需要记录进过栈的元素，避免死循环的出现！！！

发生死循环过程如下图：

🔆 7.2.1 非递归实现->代码

class Solution {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> list = new ArrayList<>();Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;//prev指向被打印过的节点TreeNode prev = null;//注意这里的循环条件//因为后续cur为空时要弹出栈顶元素，故栈不能为空//且一开始时栈为空，故cur不为空就可进入循环//当栈空且cur为空，说明前序遍历已完成while (cur != null || !stack.isEmpty()) {//cur走左子树while (cur != null) {stack.push(cur);cur = cur.left;}//当cur为空时，不可直接将栈顶元素弹出和添加进顺序表//要判断栈顶元素（根节点）是否有右孩子//若右孩子为空可以弹出和添加//若右孩子不为空，需要先将右子树的元素入栈并添加TreeNode top = stack.peek();//当栈顶元素的右孩子入过栈时，此时栈顶元素可以弹出并添加进顺序表if(top.right == null || top.right == prev) {stack.pop();list.add(top.val);prev = top;}else {cur = top.right;}}return list;}
}