数据结构之二叉树及面试题讲解（二）+https://developer.aliyun.com/article/1413554
3.翻转二叉树
思路分析
还是利用子问题思路，交换root的左右子树，再去更新root，继续交换左右子树
https://leetcode.cn/problems/invert-binary-tree/submissions/
代码实现
public TreeNode invertTree(TreeNode root) { if(root == null) return root; // 交换 TreeNode tmp = root.left; root.left = root.right; root.right = tmp; // 交换根节点的左子树和右子树 invertTree(root.left); invertTree(root.right); return root; }
4.判断平衡二叉树
https://leetcode.cn/problems/balanced-binary-tree/submissions/
1.遍历每一个节点 判断其左右子树是否平衡 只要求出当前结点左右子树的高度即可 同时还要保证其余节点也平衡
// 求树的高度 private int getHeight(TreeNode root) { if(root == null) return 0; int leftHeight = getHeight(root.left); int rightHeight = getHeight(root.right); return leftHeight > rightHeight ? leftHeight+1 : rightHeight+1; } public boolean isBalanced(TreeNode root) { if(root == null) return true; int leftHeight = getHeight(root.left); int rightHeight = getHeight(root.right); // 高度平衡的条件 每颗结点都要高度平衡 即每颗结点的左右子树的高度差都要<=1 return Math.abs(leftHeight-rightHeight) <= 1 && isBalanced(root.left) && isBalanced(root.right); }
第一种方法时间复杂度达到了0(N^2),究其原因，在于在计算高度的时候发生了重复计算，在你求完root当前的高度之后还需要再去判断其左右子树是否平衡，判断的时候还需要再去求一遍高度，导致时间复杂度过高，我们发现，在求第一次高度时，整个求高度的过程中已经发现了不平衡的现象，我们可以在返回高度的过程中就去判断是否是平衡的
2.第二种思路
// 求树的高度 private int getHeight(TreeNode root) { if(root == null) return 0; int leftHeight = getHeight(root.left); int rightHeight = getHeight(root.right); // 返回正常高度的条件 if(leftHeight >= 0 && rightHeight >= 0 && Math.abs(leftHeight-rightHeight) <= 1) { return Math.max(leftHeight,rightHeight)+1; }else { return -1; } } public boolean isBalanced(TreeNode root) { if(root == null) return true; return getHeight(root) >= 0; }
正常返回高度的条件是
- 左树高度和右树高度的绝对值之差 <= 1
- 左子树的高度符合条件 即左子树的高度不是-1
- 右子树的高度符合条件 即右子树的高度不是-1
这道题曾经是字节面试出的一道题，第一种思路很容易想到，即通过求当前结点的左右子树的高度的绝对值之差来判断是否符合条件，同时还要满足当前结点的左子树和右子树也符合条件(这一点也容易忽视)，但这种思路存在着重复计算的问题 ，时间复杂度过高；
重复计算的是高度，那能不能在一次求高度的过程中就判断是否符合条件?答案是可以的，就是提供的第二种思路
这种在过程中判断是否符合条件从而减少计算量的思路经常出现，也不容易实现，可以好好学习，总结一下
5.二叉树的遍历
思路分析：
本题是根据前序遍历的方式去创建二叉树，本质上还是利用递归的方式去创建树
先创建当前的根节点，再去创建结点的左树，最后创建结点的右树
代码实现
import java.util.Scanner; // 结点的信息需要自行创建 class TreeNode { char val; TreeNode left; TreeNode right; public TreeNode() {}; public TreeNode(char val) { this.val = val; }; } // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); // 注意 hasNext 和 hasNextLine 的区别 while (in.hasNextLine()) { // 注意 while 处理多个 case String s = in.nextLine(); // 获取创建树的根节点 TreeNode root = createTree(s); // 中序遍历 inOrder(root); } } public static int i = 0; // 根据前序遍历的结果创建一棵树 public static TreeNode createTree(String s) { TreeNode root = null; if(s.charAt(i) != '#') { // 不是#号，证明就是一个结点 实例化一个结点 i++ 再去分别创建该节点的左树，右树 root = new TreeNode(s.charAt(i)); i++; root.left = createTree(s); root.right = createTree(s); }else {// 是# 直接i++ i++; } // 递归到最后要把节点之间联系起来 所以返回root return root; } // 中序遍历 public static void inOrder(TreeNode root) { if(root == null) return; inOrder(root.left); System.out.print(root.val + " "); inOrder(root.right); } }
6.前序+中序构造二叉树
https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
代码实现
//** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public TreeNode buildTree(int[] preorder, int[] inorder) { return buildChildTree(preorder,inorder,0,inorder.length-1); } // 应该将pi设置为成员变量 否则在递归回退的过程中会重新返回值 public int pi; public TreeNode buildChildTree(int[] preorder,int[] inorder,int beginIndex,int endIndex) { // 1.没有左树 或者没有右树 if(beginIndex > endIndex) { return null; } // 2.创建根节点 TreeNode root = new TreeNode(preorder[pi]); // 3.在中序遍历中找到根节点 int rootIndex = find(inorder,beginIndex,endIndex,preorder[pi]); if(rootIndex == -1) return null; pi++; // 创建左子树 root.left = buildChildTree(preorder,inorder,beginIndex,rootIndex-1); // 创建右子树 root.right = buildChildTree(preorder,inorder,rootIndex+1,endIndex); return root; } private int find(int[] inorder,int beginIndex,int endIndex,int key) { for(int i = beginIndex; i <= endIndex; i++) { if(inorder[i] == key) { return i; } } // 没找到 返回-1 return -1; } }
7.后序+中序构造二叉树
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public int pi; public TreeNode buildTree(int[] inorder,int[] postorder) { pi = postorder.length-1; return buildChildTree(postorder,inorder,0,inorder.length-1); } public TreeNode buildChildTree(int[] postorder,int[] inorder,int beginIndex,int endIndex) { if(beginIndex > endIndex) { return null; } TreeNode root = new TreeNode(postorder[pi]); int rootIndex = find(inorder,beginIndex,endIndex,postorder[pi]); if(rootIndex == -1) return null; pi--; // 创建右子树 root.right = buildChildTree(postorder,inorder,rootIndex+1,endIndex); // 创建左子树 root.left = buildChildTree(postorder,inorder,beginIndex,rootIndex-1); return root; } private int find(int[] inorder,int beginIndex,int endIndex,int key) { for(int i = beginIndex; i <= endIndex; i++) { if(inorder[i] == key) { return i; } } // 没找到 返回-1 return -1; } }
总结：
前序/后序+中序都能构造出一棵二叉树，如果是前序+后序无法得到
8.最近的公共祖先
http://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if (root == null) return null; Stack<TreeNode> stack1 = new Stack<>(); Stack<TreeNode> stack2 = new Stack<>(); getPath(root, p, stack1); getPath(root, q, stack2); int sizeP = stack1.size(); int sizeQ = stack2.size(); if (sizeP > sizeQ) { int size = sizeP - sizeQ; while (size != 0) { stack1.pop(); size--; } } else { int size = sizeQ - sizeP; while (size != 0) { stack2.pop(); size--; } } // 此时两个栈的长度一致 while(!stack1.peek().equals(stack2.peek())) { stack1.pop(); stack2.pop(); } return stack1.peek(); } /** * 难点在于如何获得p，q路径上的所有节点 * 利用栈存放通过前序遍历遇到的每一个节点 判断结点的左右子树是否包含要寻找的结点 */ 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; } }
/** * 找最近的公共祖先 三种情况 * @param root * @param p * @param q * @return */ 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.lChild,p,q); TreeNode rightTree = lowestCommonAncestor(root.rChild,p,q); if(leftTree != null && rightTree != null) { // 都不为空 证明p，q在根节点的左右两侧 公共祖先只能是root return root; } else if (leftTree != null) { return leftTree; }else { return rightTree; } }
