当前位置：网站首页>二叉树 6/16 81-85
二叉树 6/16 81-85
2022-08-10 05:36:00 【吉良吉影__.】
1.二叉树展开为链表（ LeetCode 114 ）
递归 + 保存前节点的指针
/** * 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 {
TreeNode pre;//pre要定义为全局变量
public void flatten(TreeNode root) {
preOrder(root);
}
public void preOrder(TreeNode node){
if (node == null)return;
/* 不保存left、right的后果 当遍历node时，pre.right = node操作会把pre节点的右指针破换掉 这样preOrder(pre)中的preOrder(pre.right)的参数会变为原来的左节点 */
TreeNode left = node.left;//保存下node的left指针
TreeNode right = node.right;//保存node的right指针
if (pre != null){
pre.left = null;
pre.right = node;
}
pre = node;
preOrder(left);
preOrder(right);
}
}
2.将有序数组转换为二叉搜索树（ LeetCode 108 ）
方法一：
中序遍历，总是选择中间位置左边的数字作为根节点
题目中给的数组是按照升序排列的，因此可以确保数组是二叉搜索树的中序遍历序列
我们同样可以选择中间位置的右边数字作为根节点求解
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return helper(nums, 0, nums.length - 1);
}
public TreeNode helper(int[] nums, int left, int right) {
if (left > right) {
return null;
}
// 总是选择中间位置左边的数字作为根节点
int mid = (left + right) / 2;
TreeNode root = new TreeNode(nums[mid]);
root.left = helper(nums, left, mid - 1);
root.right = helper(nums, mid + 1, right);
return root;
}
}
方法二：自己的题解
构建出一颗平衡二叉树（AVL树）
这种解法没有技巧可言
本题不推荐此解法
static 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;
}
}
static class Solution {
TreeNode root;
public TreeNode sortedArrayToBST(int[] nums) {
addFirst(nums[0]);
for (int i = 1; i < nums.length; i++) {
add(root,nums[i]);
}
return root;
}
//添加首节点
public void addFirst(int val){
root = new TreeNode(val);
}
//构建平衡二叉树后续节点
public void add(TreeNode node ,int val){
if (val < node.val){
if (node.left == null){
//添加新节点
node.left = new TreeNode(val);
}
else {
add(node.left,val);
}
}
if (val >= node.val){
if (node.right == null){
//添加新节点
node.right = new TreeNode(val);
}
else {
add(node.right,val);
}
}
//左旋转
if (height(node.right) - height(node.left) > 1){
//右旋转
if (node.right != null && height(node.right.left) - height(node.right.right) > 1)
rightRotate(node.right);
leftRotate(node);
return;
}
//右旋转
if (height(node.left) - height(node.right) > 1){
if (node.left != null && height(node.left.right) - height(node.left.left) > 1)//左旋转
leftRotate(node.left);
rightRotate(node);
}
}
//求高度
public int height(TreeNode node){
if (node == null)return 0;
if (node.left == null && node.right == null)return 1;
return Math.max(height(node.left),height(node.right)) + 1;
}
//左旋转：当右子树高度 - 左子树高度 > 1 时
public void leftRotate(TreeNode node){
TreeNode left = node.left;
TreeNode right = node.right;
TreeNode newNode = new TreeNode(node.val);
newNode.left = left;
newNode.right = right.left;
node.val = right.val;
node.right = right.right;
node.left = newNode;
}
//右旋转：当左子树高度 - 右子树高度 > 1 时
public void rightRotate(TreeNode node){
TreeNode left = node.left;
TreeNode right = node.right;
TreeNode newNode = new TreeNode(node.val);
newNode.right = right;
newNode.left = left.right;
node.val = left.val;
node.left = left.left;
node.right = newNode;
}
}
3.把二叉搜索树转换为累加树（ LeetCode 538 ）
方法一：中序遍历
不推荐此解法
中序遍历二叉搜索树得到递增数列
/** * 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 {
int i;
public TreeNode convertBST(TreeNode root) {
List<Integer> list = new ArrayList<>();
inOrder(root,list);
Integer[] integers = list.toArray(new Integer[list.size()]);
for (int i = integers.length - 2; i >= 0; i--) {
integers[i] = integers[i] + integers[i + 1];
}
inOrderChange(root,integers);
return root;
}
public void inOrder(TreeNode node,List<Integer> list){
if (node == null)return;
if (node.left != null)
inOrder(node.left,list);
list.add(node.val);
if (node.right != null)
inOrder(node.right,list);
}
public void inOrderChange(TreeNode node,Integer[] arr){
if (node == null)return;
if (node.left != null)
inOrderChange(node.left,arr);
node.val = arr[i++];
if (node.right != null)
inOrderChange(node.right,arr);
}
}
方法二：逆序中序遍历
class Solution {
int count;//逆序总和
public TreeNode convertBST(TreeNode root) {
if (root == null)return root;//结束递归条件
convertBST(root.right);//先右
//然后根
root.val += count;
count = root.val;
convertBST(root.left);//最后左
return root;
}
}
4.删除二叉搜索树中的节点（ LeetCode 450 ）
/** * 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 deleteNode(TreeNode root, int key) {
if (root == null) {
return null;
}
if (root.val > key) {
root.left = deleteNode(root.left, key);
return root;
}
if (root.val < key) {
root.right = deleteNode(root.right, key);
return root;
}
if (root.val == key) {
if (root.left == null && root.right == null) {
//叶子节点
return null;
}
if (root.right == null) {
//单孩子
return root.left;
}
if (root.left == null) {
//单孩子
return root.right;
}
//双孩子
TreeNode successor = root.right;//root右侧最小值
while (successor.left != null) {
successor = successor.left;
}
root.right = deleteNode(root.right, successor.val);//最小值肯定只有单孩子
successor.right = root.right;//最小值替换root节点
successor.left = root.left;
return successor;
}
return root;
}
}
5.完全二叉树的节点个数（ LeetCode 222 ）
二分查找 + 位运算
/** * 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 countNodes(TreeNode root) {
if (root == null) {
return 0;
}
int level = 0;
TreeNode node = root;
while (node.left != null) {
level++;
node = node.left;
}
int low = 1 << level,//最少节点个数
high = (1 << (level + 1)) - 1;//最多节点个数
while (low < high) {
int mid = (high - low + 1) / 2 + low;
if (exists(root, level, mid)) {
low = mid;
} else {
high = mid - 1;
}
}
return low;
}
//k 二进制 110
//不计算首位1
//首位1之后，0走左边，1走右边
public boolean exists(TreeNode root, int level, int k) {
int bits = 1 << (level - 1);
TreeNode node = root;
while (node != null && bits > 0) {
if ((bits & k) == 0) {
node = node.left;
} else {
node = node.right;
}
bits >>= 1;
}
return node != null;
}
}
边栏推荐
- Exploratory Data Analysis EDA
- LeetCode 162. Finding Peaks (Moderate)
- 浅谈《帧同步网络游戏》之“框架”实现思路
- LeetCode refers to offer 10-I. Fibonacci sequence (simple)
- I don't like my code
- pytorch-11. Convolutional Neural Network (Advanced)
- 氨氮的有效吸附材料
- Pytorch - 07. Multidimensional characteristics of input processing
- 21天学习挑战赛--图像物体的边界
- Gradle学习 (一) 入门
猜你喜欢
Deep learning TensorFlow entry environment configuration
从零开始构建Google Protocol Buffer / protobuf 的helloworld工程(超级详细)
STM32F407ZG PWM
详解 Hough 变换（下）圆形检测
STC12C5A60S2单片机WIFI信号扫描报警监视系统信号增强信号过低报警
在Unity的Update中通过物体自身位置判断运动方向
每日刷题（day01）——leetcode 53. 最大子数组和
【接口自动化】
开源游戏服务器框架NoahGameFrame（NF）客户端环境搭建(三)
LeetCode 2011.执行操作后的变量值（简单）
随机推荐
Explain the principle of MySql index in detail
视差映射：更逼真的纹理细节表现（上）：为什么要使用视差映射
mkfs.minix.c之minix_super_block.s_ninodes获取解析
51单片机RS485远程双机多机温度采集主从机多节点蜂鸣器报警
在Unity的Update中通过物体自身位置判断运动方向
为什么游戏需要热更新
mysql使用常见问题和解决
LeetCode refers to the offer 21. Adjust the order of the array so that the odd numbers are in front of the even numbers (simple)
废水中氟离子去除方法
Exploratory Data Analysis EDA
LeetCode 1720. Decoding XORed Arrays (Simple)
氨氮吸附工艺
【简易笔记】PyTorch官方教程简易笔记 EP1
51单片机ST188手持人体温度脉搏心率测量仪锂电池充电
二叉树 6/20 86-90
自定义View的流程总结学习
STM32F407ZG PWM
Notes for Netual Network
电路建模的要点
详解 Hough 变换（上）基本原理与直线检测