二叉树
BM23 二叉树的前序遍历
public class Solution {
List<Integer> list = new ArrayList<>();
public int[] preorderTraversal (TreeNode root) {
orderTraversal(root);
int[] arr = new int[list.size()];
int i = 0;
for(Integer each : list) arr[i++] = each;
return arr;
}
public void orderTraversal(TreeNode root){
if(root == null) return;
/****************前序遍历*******************/
list.add(root.val);
orderTraversal(root.left);
orderTraversal(root.right);
/*******************************************/
}
}
BM24 二叉树的中序遍历
public class Solution {
List<Integer> list = new ArrayList<>();
public int[] inorderTraversal (TreeNode root) {
orderTraversal(root);
int[] arr = new int[list.size()];
int i = 0;
for(Integer each : list) arr[i++] = each;
return arr;
}
public void orderTraversal(TreeNode root){
if(root == null) return;
/****************中序遍历*******************/
orderTraversal(root.left);
list.add(root.val);
orderTraversal(root.right);
/*******************************************/
}
}
BM25 二叉树的后序遍历
public class Solution {
List<Integer> list = new ArrayList<>();
public int[] inorderTraversal (TreeNode root) {
orderTraversal(root);
int[] arr = new int[list.size()];
int i = 0;
for(Integer each : list) arr[i++] = each;
return arr;
}
public void orderTraversal(TreeNode root){
if(root == null) return;
/****************后序遍历*******************/
orderTraversal(root.left);
orderTraversal(root.right);
list.add(root.val);
/*******************************************/
}
}
BM26 二叉树的层序遍历
public class Solution {
// BFS算法
ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
if(root == null) return res;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
ArrayList<Integer> list = new ArrayList<>();
int size = queue.size();
for(int i = 0; i < size; i++){
TreeNode node = queue.poll();
list.add(node.val);
if(node.left != null) queue.offer(node.left);
if(node.right != null) queue.offer(node.right);
}
res.add(list);
}
return res;
}
}
BM27 按之字形顺序打印二叉树
public class Solution {
ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
public ArrayList<ArrayList<Integer>> Print (TreeNode root) {
if(root == null) return res;
/********************注意！！！采用双向链表*******************************/
LinkedList<TreeNode> queue = new LinkedList<>();
queue.add(root);
// 分层遍历，level用于标记层数
int level = 1;
while(!queue.isEmpty()){
ArrayList<Integer> list = new ArrayList<>();
int size = queue.size();
if((level & 1) == 1){// 奇数层
for(int i = 0; i < size; i++){
/*******************奇数层从后面取节点************************/
TreeNode node = queue.removeLast();
list.add(node.val);
/*******************奇数层先加左后加右***********************/
if(node.left != null) queue.addFirst(node.left);
if(node.right != null) queue.addFirst(node.right);
}
}else{// 偶数层
for(int i = 0; i < size; i++){
/********************偶数层从前面取节点**********************/
TreeNode node = queue.removeFirst();
list.add(node.val);
/********************偶数层先加右后加左**********************/
if(node.right != null) queue.addLast(node.right);
if(node.left != null) queue.addLast(node.left);
}
}
level++;
res.add(list);
}
return res;
}
}
BM28 二叉树的最大深度
public class Solution {
public int maxDepth (TreeNode root) {
if(root == null) return 0;
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
}
BM29 二叉树中和为某一值的路径（一）
public class Solution {
public boolean hasPathSum (TreeNode root, int sum) {
if(root == null) return false;
sum -= root.val;
// 到达叶子结点
if(sum == 0 && root.left == null && root.right == null) return true;
// 递归左右子树
return hasPathSum(root.left, sum) || hasPathSum(root.right, sum);
}
}
BM30 二叉搜索树与双向链表（注意）
方法一：非递归版
解题思路：
1.核心是中序遍历的非递归算法。
2.修改当前遍历节点与前一遍历节点的指针指向。
import java.util.Stack;
public class Solution {
// 方法一：中序遍历的非递归算法
public TreeNode Convert(TreeNode root) {
if(root == null) return null;
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode p = root;
TreeNode pre = null;// 用于保存中序遍历序列的上一节点
boolean isFirst = true;
while(p != null || !stack.isEmpty()){
while( p != null){
stack.push(p);
p = p.left;
}
p = stack.pop();
if(isFirst){
root = p;// 将中序遍历序列中的第一个节点记为root
pre = root;
isFirst = false;
}else{
pre.right = p;
p.left = pre;
pre = p;
}
p = p.right;
}
return root;
}
}
方法二：递归版
解题思路：
1.将左子树构造成双链表，并返回链表头节点。
2.定位至左子树双链表最后一个节点。
3.如果左子树链表不为空的话，将当前root追加到左子树链表。
4.将右子树构造成双链表，并返回链表头节点。
5.如果右子树链表不为空的话，将该链表追加到root节点之后。
6.根据左子树链表是否为空确定返回的节点。
public class Solution {
// 记录子树链表的最后一个节点，终结点只可能为只含左子树的非叶节点与叶节点
protected TreeNode leftLast = null;
public TreeNode Convert(TreeNode root) {
if(root == null) return null;
if(root.left == null && root.right == null){
leftLast = root;// 最后的一个节点可能为最右侧的叶节点
return root;
}
// 1.将左子树构造成双链表，并返回链表头节点
TreeNode left = Convert(root.left);
// 3.如果左子树链表不为空的话，将当前root追加到左子树链表
if(left != null){
leftLast.right = root;
root.left = leftLast;
}
leftLast = root;// 当根节点只含左子树时，则该根节点为最后一个节点
// 4.将右子树构造成双链表，并返回链表头节点
TreeNode right = Convert(root.right);
// 5.如果右子树链表不为空的话，将该链表追加到root节点之后
if(right != null){
right.left = root;
root.right = right;
}
return left != null ? left : root;
}
}
BM31 对称的二叉树
public class Solution {
boolean isSymmetrical(TreeNode pRoot) {
// 根节点为null
if(pRoot == null) return true;
// 判断左右子树是否对称
return isSymmetrical(pRoot.left, pRoot.right);
}
boolean isSymmetrical(TreeNode root1, TreeNode root2) {
// 两个子树均为null
if(root1 == null && root2 == null) return true;
// 其中一个子树为null
if(root1 == null || root2 == null) return false;
// 左右子节点不相等
if(root1.val != root2.val) return false;
return isSymmetrical(root1.right, root2.left) && isSymmetrical(root1.left, root2.right);
}
}
BM32 合并二叉树
public class Solution {
public TreeNode mergeTrees (TreeNode t1, TreeNode t2) {
// 合并到t1中，输出t1子树
// 若t1和t2均为null，则返回null
if(t1 == null && t2 == null) return null;
// 若t1为null，则返回t2
// 若t2为null，则返回t1
if(t1 == null) return t2;
if(t2 == null) return t1;
// 若t1和t2均不为null，则合并值
t1.val += t2.val;
// 继续合并左右子树
t1.left = mergeTrees(t1.left, t2.left);
t1.right = mergeTrees(t1.right, t2.right);
return t1;
}
}
BM33 二叉树的镜像
public class Solution {
public TreeNode Mirror (TreeNode pRoot) {
// 空节点，无需转换
if(pRoot == null) return null;
// 继续转换左右子树
pRoot.left = Mirror(pRoot.left);
pRoot.right = Mirror(pRoot.right);
// 交换左右子树
TreeNode node = pRoot.right;
pRoot.right = pRoot.left;
pRoot.left = node;
return pRoot;
}
}
BM34 判断是不是二叉搜索树
public class Solution {
public boolean isValidBST (TreeNode root) {
// 空节点，返回true
if(root == null) return true;
// 单节点，返回true
if(root.left == null && root.right == null) return true;
// 左子树为null，并且根节点的值小于右节点的值，则取决于右子树
if(root.left == null && root.right.val > root.val) return isValidBST(root.right);
// 右子树为null，并且根节点的值大于左节点的值，则取决于左子树
if(root.right == null && root.left.val < root.val) return isValidBST(root.left);
// 左右子树均不为null
if(root.left.val > root.val || root.right.val < root.val) return false;
// 判断前驱节点是否小于根节点，后继节点是否大于根节点
return maxLeftTree(root.left, Integer.MIN_VALUE) < root.val && minRightTree(root.right, Integer.MAX_VALUE) > root.val;
}
public int maxLeftTree(TreeNode root, int ans){
if(root == null) return ans;
while(root.right != null){
root = root.right;
ans = Math.max(ans, root.val);
}
return ans;
}
public int minRightTree(TreeNode root, int ans){
if(root == null) return ans;
while(root.left != null){
root = root.left;
ans = Math.max(ans, root.val);
}
return ans;
}
}
BM35 判断是不是完全二叉树
public class Solution {
public boolean isCompleteTree (TreeNode root) {
// 对于完全二叉树的结束位置前的所有节点一定非null
if(root == null) return true;
// BFS算法
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
// 标记是否结束
boolean end = false;
while(!queue.isEmpty()){
int size = queue.size();
for(int i = 0; i < size; i++){
TreeNode node = queue.poll();
if(node == null) {
// 修改状态，跳过本次循环
end = true;
continue;
}
// 如果再次进入循环，说明当前为null的节点并非结束，则该树不是完全二叉树
if(end) return false;
queue.offer(node.left);
queue.offer(node.right);
}
}
return true;
}
}
BM36 判断是不是平衡二叉树
public class Solution {
public boolean IsBalanced_Solution(TreeNode root) {
if(root == null) return true;
// 计算左右子树的最大深度
int leftDepth = maxDepth(root.left);
int rightDepth = maxDepth(root.right);
// 若高度差大于1，则非平衡二叉树
if(Math.abs(leftDepth - rightDepth) > 1) return false;
// 判断左右子树是否为平衡二叉树
return IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);
}
// 用以计算树的最大深度
public int maxDepth(TreeNode root){
if(root == null) return 0;
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
}
BM37 二叉搜索树的最近公共祖先
public class Solution {
public int lowestCommonAncestor (TreeNode root, int p, int q) {
// 统一p为小值，q为大值
if(p > q){// 交换p和q
p = p ^ q;
q = p ^ q;
p = p ^ q;
}
if(p <= root.val && q >= root.val) return root.val;
if(q < root.val) return lowestCommonAncestor(root.left, p, q);
return lowestCommonAncestor(root.right, p, q);
}
}
BM38 在二叉树中找到两个节点的最近公共祖先
public class Solution {
/*****************************时间复杂度很高***************************************/
// public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
// // 若根节点与其中一个值相等，则为最近公共祖先
// if(root.val == o1 || root.val == o2) return root.val;
// // 若两个值均在左子树中，则最近公共祖先在左子树中
// if(search(root.left, o1) && search(root.left, o2)) return lowestCommonAncestor(root.left, o1, o2);
// // 若两个值均在右子树中，则最近公共祖先在右子树中
// if(search(root.right, o1) && search(root.right, o2)) return lowestCommonAncestor(root.right, o1, o2);
// // 一个值在左子树，一个值在右子树，则根节点即为最近公共祖先
// return root.val;
// }
// // 查找目标值
// public boolean search(TreeNode root, int target){
// if(root == null) return false;
// if(root.val == target) return true;
// return search(root.left, target) || search(root.right, target);
// }
/*****************************时间复杂度较低***************************************/
public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
// 若没找到任意一个值，则返回不存在-1
if(root == null) return -1;
// 若根节点与其中一个值相等，则返回当前值
if(root.val == o1 || root.val == o2) return root.val;
// 在左子树中查找
int left = lowestCommonAncestor(root.left, o1, o2);
// 在右子树中查找
int right = lowestCommonAncestor(root.right, o1, o2);
// 一个值在左子树，一个值在右子树，则根节点即为最近公共祖先
if(left != -1 && right != -1) return root.val;
// 否则，两个都在左子树中，或者两个都在右子树中
// 若两个都在左子树中，则返回右子树中找到的值；若两个都在右子树中，则返回左子树中找到的值
return left == -1 ? right : left;
}
}
BM39 序列化二叉树
import java.util.*;
public class Solution {
private static String SPLIT = ",";
private static String NULL = "#";
String Serialize(TreeNode root) {
// 采用动态字符串存储序列化字符串
StringBuilder str = new StringBuilder();
// 序列化
Serialize(root, str);
// 将动态字符串转化为字符串
return str.toString();
}
void Serialize(TreeNode root, StringBuilder str){
if(root == null) {
str.append(NULL).append(SPLIT);
return;
}
/*******************前序遍历位置************************/
str.append(root.val).append(SPLIT);
Serialize(root.left, str);
Serialize(root.right, str);
}
TreeNode Deserialize(String str) {
// 将字符串转化为链表
LinkedList<String> nodes = new LinkedList<>();
for(String s : str.split(SPLIT)){
nodes.addLast(s);
}
// 反序列化
return Deserialize(nodes);
}
TreeNode Deserialize(LinkedList<String> nodes){
if(nodes.isEmpty()) return null;
/*******************前序遍历位置************************/
// 链表最左边的就是根节点
String first = nodes.removeFirst();
if(first.equals(NULL)) return null;
// 构建根节点
TreeNode root = new TreeNode(Integer.parseInt(first));
// 构建左右子树
root.left = Deserialize(nodes);
root.right = Deserialize(nodes);
return root;
}
}
BM40 重建二叉树
public class Solution {
HashMap<Integer, Integer> map = new HashMap<>();
public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {
if(pre.length == 0) return null;
if(pre.length == 1) return new TreeNode(pre[0]);
// 将vin中的索引存储在map中，方便查找根节点的位置
for(int i = 0; i < vin.length; i++){
map.put(vin[i], i);
}
// 构建二叉树
return reConstructBinaryTree(pre, 0, pre.length - 1, vin, 0, vin.length - 1);
}
public TreeNode reConstructBinaryTree(int[] pre, int preStart, int preEnd, int[] vin, int inStart, int inEnd) {
if(preStart > preEnd || inStart > inEnd) return null;
// 构建根节点
TreeNode root = new TreeNode(pre[preStart]);
// 查找根节点在中序遍历数组中的索引位置
int index = map.get(pre[preStart]);
// 构建左子树，注意确定索引位置，index - inStart 为左子树的长度
root.left = reConstructBinaryTree(pre, preStart + 1, preStart + index - inStart, vin, inStart, index - 1);
// 构建右子树
root.right = reConstructBinaryTree(pre, preStart + index - inStart + 1, preEnd, vin, index + 1, inEnd);
return root;
}
}
BM41 输出二叉树的右视图
import java.util.*;
public class Solution {
List<Integer> res = new ArrayList<>();// 用于层序遍历
HashMap<Integer, Integer> map = new HashMap<>();
public int[] solve (int[] xianxu, int[] zhongxu) {
if(xianxu.length == 0) return null;
if(xianxu.length == 1) return xianxu;
// 构建二叉树
for(int i = 0; i < zhongxu.length; i++){
map.put(zhongxu[i], i);
}
TreeNode root = reConstructBinaryTree(xianxu, 0, xianxu.length - 1, zhongxu, 0, zhongxu.length - 1);
/*************************层序遍历****************************/
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
// 记录每一层的最后一个节点值
int number = 0;
int size = queue.size();
for(int i = 0; i < size; i++){
TreeNode node = queue.poll();
number = node.val;// 更新number
if(node.left != null) queue.offer(node.left);
if(node.right != null) queue.offer(node.right);
}
// 将每一层的最后一个节点值放入链表
res.add(number);
}
// 将链表中的值迁移到数组
int[] nums = new int[res.size()];
int i = 0;
for(Integer num : res) nums[i++] = num;
/************************************************************/
// 返回结果
return nums;
}
public TreeNode reConstructBinaryTree(int[] pre, int preStart, int preEnd, int[] vin, int inStart, int inEnd) {
if(preStart > preEnd || inStart > inEnd) return null;
// 构建根节点
TreeNode root = new TreeNode(pre[preStart]);
// 查找根节点在中序遍历数组中的索引位置
int index = map.get(pre[preStart]);
// 构建左子树，注意确定索引位置，index - inStart 为左子树的长度
root.left = reConstructBinaryTree(pre, preStart + 1, preStart + index - inStart, vin, inStart, index - 1);
// 构建右子树
root.right = reConstructBinaryTree(pre, preStart + index - inStart + 1, preEnd, vin, index + 1, inEnd);
return root;
}
}
华为工作强度 817人发布
