🎄3. 给定一个二叉树,找到该树中两个指定节点的最近公共祖先
题目:
思路:
祖先的定义: 若节点 p 在节点 root 的左(右)子树中,或 p = root ,则称 root 是 p 的祖先。
根据以上定义,若 root 是 p,q 的 最近公共祖先 ,则只可能为以下情况之一:
①p 和 q 在 root的子树中,且分列 root 的 异侧(即分别在左、右子树中);
②p = root ,且 q 在 root 的左或右子树中;
③q = root ,且 p 在 root 的左或右子树中;
考虑通过递归对二叉树进行先序遍历,当遇到节点 p 或 q 时返回。从底至顶回溯,当节点 p,q 在节点 root的异侧时,节点 root 即为最近公共祖先,则向上返回 root 。
实现代码:
class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if(root==null) return null;//根节点空的话,直接返回null,无公共祖先 if(root==p || root == q) return root;//如果q或者p就是根节点,那直接返回,此时他们就是最近公共祖先 //一开始的根节点不是祖先就往下遍历左右子树 //递归左树找目标点q和p,找到的话会返回找到的节点,没找到则返回空 TreeNode leftTree = lowestCommonAncestor(root.left,p,q); //递归右树找目标点q和p,找到的话会返回找到的节点,没找到则返回空 TreeNode rightTree = lowestCommonAncestor(root.right,p,q); //如果两边都找到了目标点(q/p)那么当前这个节点就是最近祖先 if(leftTree!=null && rightTree!=null){ return root; } //代码走到这里说明有一个为空(没找到目标点) //只有左边找到了目标点(q/p),那当前根节点的左节点就是最近祖先 if(leftTree!=null){ return leftTree; } //只有右边找到了目标点(q/p),那当前根节点的右节点就是最近祖先 if(rightTree!=null){ return rightTree; } //没有找到目标点q或者p return null; } }
🎄4. 二叉树搜索树转换成排序双向链表
题目:
思路:
- 已知将二叉搜索树进行中序遍历可以得到
由小到大的顺序排列
,因此本题最直接的想法就是进行中序遍历
。 - 根据题目的要求1,不能创建新的结点,所以我们
设置一个pre用于指向前驱节点
- 例如root为指向10的时候,preNode指向8,如图所示:
实现代码:
public class Solution { public TreeNode pre = null;//因为是要递归,所以pre要设在外部 public void ConvertChild(TreeNode pcur) { if(pcur==null){ return; } ConvertChild(pcur.left);//因为是中序遍历,所以先递归左节点 //处理根节点 //关键点 pcur.left=pre;//当前节点的左指针指向前驱节点 if(pre!=null){//如果前驱节点非空 pre.right=pcur;//前驱节点右指针指向当前节点 } pre=pcur;//pre走到当前节点,也就是当前节点成为下一个节点的前驱节点 //三行代码,关键点 ConvertChild(pcur.right);//递归左节点 } public TreeNode Convert(TreeNode pRootOfTree) { if(pRootOfTree==null) return null; ConvertChild(pRootOfTree); TreeNode head = pRootOfTree; while(head.left!=null){ head=head.left; } return head; } }
🎄5. 根据一棵树的前序遍历与中序遍历构造二叉树
题目:
思路:
- 所以我们只需要根据先序遍历得到根节点,然后在中序遍历中找到根节点的位置,它的左边就是左子树的节点,右边就是右子树的节点。
- 递归生成左子树和右子树
实现代码:
class Solution { public int preindex = 0; public TreeNode buildTreeChild(int[] preorder,int[] inorder,int inbegin,int inend) { if(inbegin > inend) { return null;//左树 或者 右树 为空 } TreeNode root = new TreeNode(preorder[preindex]); //找根节点在中序遍历的数组中的结果 int rootIndex = findRootIndex(inorder,inbegin,inend,preorder[preindex]); preindex++; //构建 左树 root.left = buildTreeChild(preorder,inorder,inbegin,rootIndex-1); //构建 右树 root.right = buildTreeChild(preorder,inorder,rootIndex+1,inend); return root; } //就是一个数组当中的查找代码 public int findRootIndex(int[] inorder,int inbegin,int inend,int key) { for(int i = inbegin;i <= inend;i++) { if(inorder[i] == key) { return i; } } return -1; } public TreeNode buildTree(int[] preorder, int[] inorder) { if(preorder == null || inorder == null) return null; return buildTreeChild(preorder,inorder,0,inorder.length-1); } }
🎄6. 根据一棵树的中序遍历和后序遍历构造二叉树
题目:
思路:
- 和上题几乎一样,只需要
几处小改动
- 因为是给的是
后续遍历
,所以构建的时候,读取后续遍历数组要从后往前读取
,并且构建的时候是根->右->左
实现代码:
class Solution { public int postindex = 0; public 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]); postindex--;//从后往前 //构建右树 root.right = buildTreeChild(postorder,inorder,rootIndex+1,inend); //构建左树 root.left = buildTreeChild(postorder,inorder,inbegin,rootIndex-1); return root; } //就是一个数组当中的查找代码 public int findRootIndex(int[] inorder,int inbegin,int inend,int key) { for(int i = inbegin;i <= inend;i++) { if(inorder[i] == key) { return i; } } return -1; } public TreeNode buildTree(int[] inorder, int[] postorder) { postindex = postorder.length-1;//将后序遍历数组的下标设为长度-1,即最后一个位置,好让其从后往前遍历数组 if(postorder == null || inorder == null) return null; return buildTreeChild(postorder,inorder,0,inorder.length-1); } }
🎄7. 二叉树创建字符串
题目:
思路:
- 我们可以使用递归的方法得到二叉树的前序遍历。在递归时,根据题目描述,我们需要加上额外的括号,会有以下 4 种情况:
① 如果当前节点有两个孩子
,那我们在递归时,需要在两个孩子的结果外都加上一层括号;
②如果当前节点没有孩子
,那我们不需要在节点后面加上任何括号
;
③如果当前节点只有左孩子
,那我们在递归时,只需要在左孩子的结果外加上一层括号,而不需要给右孩子加上任何括号
;
④如果当前节点只有右孩子
,那我们在递归时,需要先加上一层空的括号 () 表示左孩子为空
,再对右孩子进行递归,并在结果外加上一层括号。
考虑完上面的 4 种情况,我们就可以得到最终的字符串。
实现代码:
class Solution { public void tree2strChild(TreeNode root,StringBuilder sb) { if(root == null) return ; sb.append(root.val);//前序遍历,先将根节点加入可变字符串 if(root.left==null){//左树为空,还得考虑右树的情况 if(root.right==null){//如果右树为空,说明当前根节点没有孩子 //直接返回,因为题目要求把不必要的()省略 return; }else{//右树不为空,加(),这里还在左树,这个()是表示左子树为空 //因为右树不为空,所有不能省略 sb.append("()"); } }else{//左树不为空,先加(,然后继续遍历左树,再加) sb.append("("); tree2strChild(root.left,sb); sb.append(")"); } //左树遍历完要遍历右树了 if(root.right==null){//如果右树为空 return;//直接返回,因为省略()不会影响字符串与树的映射关系 }else{//否则,先加(,然后继续遍历右树,再加) sb.append("("); tree2strChild(root.right,sb); sb.append(")"); } } public String tree2str(TreeNode root) { if(root==null) return null; StringBuilder sb = new StringBuilder(); tree2strChild(root,sb); return sb.toString(); } }