【算法日记】二叉树：转换双向链表，层序遍历，找公共祖先，构建二叉树
·
文章目录
1. 二叉搜索树与双向链表（BM30）
题目描述
解题思路
题目要求返回一个固定节点，而递归调用是多次的，所以要分成两个方法。
- ConvertChild（）：
- 搜索二叉树的特点是：中序遍历得到的结果是有序的 所以要采用中序遍历。
- prev来记录前一个节点。prev必须是类变量，不可以是局部变量，因为递归调用会重复把prev置空。
- 转换成双向链表，left和right就代表逻辑链表节点上的左右。当前节点的left置为prev，prev（不为空的情况下）的right置为root。prev置为root
- 此时题目给的pRootOfTree是链表的中心，把head移到链表左端，并返回
代码示例
public class Solution {
TreeNode prev = null;
public TreeNode Convert(TreeNode pRootOfTree) {
if (pRootOfTree == null)
return null;
ConvertChild(pRootOfTree);
TreeNode head = pRootOfTree;
while (head.left != null)
head = head.left;
return head;
}
public void ConvertChild(TreeNode root) {
if (root == null)
return ;
ConvertChild(root.left);
if (prev != null)
prev.right = root;
root.left = prev;
prev = root;
ConvertChild(root.right);
}
}
2. 二叉树遍历（KY11）
题目描述
解题思路
createTree（）:遍历字符串，因为函数要循环调用，字符串要依次遍历，所以下标i应该是类变量而非局部变量。- 如果字符不是
#，则创建新节点，i自增，接着创建左树和右树 - 如果字符是
#，则i自增，不创建节点。此时root还是null，返回上一个函数。 - main函数：先调用
createTree（），再中序遍历二叉树，输出字符 - 为了防止牛客网给出多组测试字符串造成
i过大，i要手动置为0
代码示例
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNext()) {
String str = in.nextLine();
TreeNode node = createTree(str);
inOrder(node);
i = 0;
}
}
public static int i = 0;
static TreeNode createTree(String str){
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;
}
static void inOrder(TreeNode root){
if(root==null)
return;
inOrder(root.left);
System.out.print(root.val+" ");
inOrder(root.right);
}
}
3. 二叉树的层序遍历（LC102）
题目描述
解题思路
当队列不为空时，循环处理每一层：
- 先获取当前队列大小，即当前层的节点数量
- 创建一个临时列表存储当前层的节点值
- 循环取出当前层的所有节点（循环次数为当前层节点数）：
- 取出队首节点，将其值加入临时列表
- 如果该节点有左子节点，将左子节点入队
- 如果该节点有右子节点，将右子节点入队
- 当前层处理完毕后，将临时列表加入结果列表
代码示例
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ret = new ArrayList<>();
if(root==null)
return ret;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
int size = queue.size();
List<Integer> list = new ArrayList<>();
while(size!=0){
TreeNode cur = queue.poll();
list.add(cur.val);
if(cur.left!=null)
queue.offer(cur.left);
if(cur.right!=null)
queue.offer(cur.right);
size--;
}
ret.add(list);
}
return ret;
}
4. 二叉树的公共祖先(LC236)
题目描述
解题思路
思路一：
可以分成三种情况：
- 根节点root就是p或q 直接返回root
- p和q分别在左树和右树
- p和q都在左树或都在右树
分别定义 leftTree ，rightTree 在子树中遍历，如果两个都不是空，证明p，q在左右两侧，那么root就是最小公共祖先；如果其中一个为空，证明p，q在同一侧，返回已找到的公共祖先。
思路二：
利用栈存储从根节点到p和q的路径，找公共节点
- getPath（）：先让root入栈，如果node是root，返回true；接着在左右子树寻找路径，如果左右子树中都没有，说明当前节点不是到达node的经过的节点，出栈。
代码示例
- 思路一：
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root==null)
return null;
if(p==root||q==root)
return root;
TreeNode leftTree = lowestCommonAncestor(root.left,p,q);
TreeNode rightTree = lowestCommonAncestor(root.right,p,q);
if(leftTree!=null&&rightTree!=null)
return root;
else if(leftTree!=null)
return leftTree;
else
return rightTree;
}
- 思路二：
boolean getPath(TreeNode node,TreeNode root, Stack<TreeNode> stack){
if(root==null)
return false;
stack.push(root);
if(root==node)
return true;
boolean ret = getPath(node,root.left,stack);
if(ret)
return true;
ret = getPath(node,root.right,stack);
if(ret)
return true;
stack.pop();
return false;
}
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root==null)
return null;
Stack<TreeNode> s1 = new Stack<>();
Stack<TreeNode> s2 = new Stack<>();
getPath(p,root,s1);
getPath(q,root,s2);
int size1 = s1.size();
int size2 = s2.size();
if(size1>size2){
int size = size1-size2;
while(size!=0){
s1.pop();
size--;
}
}else{
int size = size2-size1;
while(size!=0){
s2.pop();
size--;
}
}
while(!s1.isEmpty()){
TreeNode tmp1 = s1.pop();
TreeNode tmp2 = s2.pop();
if(tmp1==tmp2){
return tmp1;
}
}
return null;
}
5. 从前序和中序遍历序列构建二叉树（LC105）
题目描述
解题思路
为了便于递归下标参数的传递，另写一个函数。
前序遍历确定根节点，所以先创建根节点，在中序数组中找到根节点值的下标，下一次传参时创建左树的右边界就是preIndex-1；创建右树的左边界就是preIndex+1。
代码示例
int preIndex;
public TreeNode buildTree(int[] preorder, int[] inorder) {
return buildTreeChile(preorder,inorder,0,inorder.length-1);
}
public TreeNode buildTreeChile(int[] preorder,int[] inorder,int inBegin,int inEnd){
if(inBegin>inEnd)
return null;
TreeNode root = new TreeNode(preorder[preIndex]);
int rootIndex = getIndex(preorder[preIndex],inorder,inBegin,inEnd);
preIndex++;
root.left = buildTreeChile(preorder,inorder,inBegin,rootIndex-1);
root.right = buildTreeChile(preorder,inorder,rootIndex+1,inEnd);
return root;
}
int getIndex(int val,int[] inorder,int inBegin,int inEnd){
for(int i =inBegin;i<=inEnd;i++ ){
if(inorder[i]==val)
return i;
}
return -1;
}
6. 从中序和后序遍历序列构建二叉树（LC106）
题目描述
解题思路
与上一题的解法类似。需要注意的是：后序遍历的顺序是左 右 根，所以要在后序数组中从后往前遍历，先确定根节点，再创建右树，再创建左子树。
代码示例
int postIndex;
public TreeNode buildTree(int[] inorder, int[] postorder) {
postIndex = postorder.length-1;
return buildTreeChild(inorder,postorder,0,inorder.length-1);
}
public TreeNode buildTreeChild(int[] inorder,int[] postorder,int inBegin,int inEnd){
if(inBegin>inEnd)
return null;
TreeNode root = new TreeNode(postorder[postIndex]);
int rootIndex = getIndex(postorder[postIndex],inorder,inBegin,inEnd);
postIndex--;
root.right = buildTreeChild(inorder,postorder,rootIndex+1,inEnd);
root.left = buildTreeChild(inorder,postorder,inBegin,rootIndex-1);
return root;
}
int getIndex(int val,int[] inorder,int inBegin,int inEnd){
for(int i =inBegin;i<=inEnd;i++ ){
if(inorder[i]==val)
return i;
}
return -1;
}
7. 根据二叉树创建字符串（LC606）
题目描述
解题思路
为了方便函数递归传参，新写一个函数。
- 先添加root的值，再判断左树，如果左树不为空，添加左括号，递归调用添加左数的值，添加右括号，
- 如果左树为空，再判断此时右树，右树如果也为空，就可以直接返回，如果右树不为空，那么左树的括号不能省略。
- 再单独判断右树，如果右树不为空，与左树类似，先添加左括号，再递归调用，再添加右括号
代码示例
public String tree2str(TreeNode root) {
StringBuilder ret = new StringBuilder();
tree2strChild(root,ret);
return ret.toString();
}
void tree2strChild(TreeNode root,StringBuilder s){
if(root==null)
return ;
s.append(root.val);
if(root.left!=null){
s.append("(");
tree2strChild(root.left,s);
s.append(")");
}else{
if(root.right!=null)
s.append("()");
else
return;
}
if(root.right!=null){
s.append("(");
tree2strChild(root.right,s);
s.append(")");
}
}
8. 非递归法前序遍历（LC144）
- 左子树（内层循环）：
- 当cur不为空时，将其入栈并访问
- 然后移动cur到其左子节点，继续上述操作
- 这个过程实现了 “根 - 左” 的访问顺序，直到左子树尽头
- 右子树处理：
- 当左子树遍历完成（cur为空），弹出栈顶节点top
- 将cur指向top的右子节点
- 此时外层循环会继续处理右子树，重复左子树的遍历逻辑
void preOrder(TreeNode root){
TreeNode cur = root;
Stack<TreeNode> stack = new Stack<>();
while(cur!=null||!stack.isEmpty()){
while(cur!=null){
stack.push(cur);
System.out.println(cur.val+" ");
cur=cur.left;
}
TreeNode top =stack.pop();
cur = top.right;
}
}
9. 非递归法中序遍历（LC94）
非递归法中序遍历
与前序遍历类似，区别在于中序遍历先访问左树，所以要在内层循环结束（也就是到左子树尽头）再弹出并访问
void inOrder(TreeNode root){
TreeNode cur = root;
Stack<TreeNode> stack = new Stack<>();
while(cur!=null||!stack.isEmpty()){
while(cur!=null){
stack.push(cur);
cur=cur.left;
}
TreeNode top =stack.pop();
System.out.println(top.val+" ");
cur = top.right;
}
}
10. 非递归法后序遍历（LC145）
后序遍历要先保证右树遍历后再访问根，所以在输出根之前，先判断右树是否为空，如果为空，输出根节点并把根节点弹出；如果不为空则把右树赋值给cur继续遍历。
- 如图，当cur为9时，右树不为空，所以把8赋值cur，此时8的右树为空，所以输出8并弹出。
- 下一轮循环中top依旧是9，这样就陷入了死循环。
- 应该记录右树是否被遍历过，输出的判断条件是右树为空或者右树被遍历过。
- 定义引用prev，当8输出的时候把8赋值给prev，这样下一轮循环中先判断prev是9的右树，再输出9.
void postOrder(TreeNode root){
TreeNode cur = root;
TreeNode prev = null;
Stack<TreeNode> stack = new Stack<>();
while(cur!=null||!stack.isEmpty()){
while(cur!=null){
stack.push(cur);
cur=cur.left;
}
TreeNode top =stack.peek();
if(top.right==null||prev==top.right){
System.out.println(top.val);
stack.pop();
prev=top;
}else{
cur=top.right;
}
}
}
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
31
0- 0
已为社区贡献7条内容
所有评论(0)