🎄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(); } }
