目录
思想
首先是要明白二叉树操作的位置，是先对元素进行操作再递归，还是先递归再对元素节点进行操作？
其实可以看出这就是前序后序两种操作——>对应在我们的排序算法中不难想到前序-快排，后序-归并
为什么？，首先是快排，若要对 nums[lo..hi] 进行排序，我们先找一个分界点 p，通过交换元素使得 nums[lo..p-1] 都小于等于 nums[p]，且 nums[p+1..hi] 都大于 nums[p]，然后递归地去 nums[lo..p-1] 和 nums[p+1..hi] 中寻找新的分界点，最后整个数组就被排序了
快排模板：
void sort(int[] nums, int lo, int hi) {
/****** 前序遍历位置 ******/
// 通过交换元素构建分界点 p
int p = partition(nums, lo, hi);
/************************/
//比较大小进行交换
sort(nums, lo, p - 1);
sort(nums, p + 1, hi);
}
归并排序，要对 nums[lo..hi] 进行排序，我们先对 nums[lo..mid] 排序，再对 nums[mid+1..hi] 排序，最后把这两个有序的子数组合并，整个数组就排好序了，排序的逻辑在后序位置
// 定义：排序 nums[lo..hi]
void sort(int[] nums, int lo, int hi) {
int mid = (lo + hi) / 2;
// 排序 nums[lo..mid]
sort(nums, lo, mid);
// 排序 nums[mid+1..hi]
sort(nums, mid + 1, hi);
/****** 后序位置 ******/
// 合并 nums[lo..mid] 和 nums[mid+1..hi]
merge(nums, lo, mid, hi);
/*********************/
}
二叉树最大深度
104. 二叉树的最大深度 - 力扣（LeetCode）
思路：1. 我们可以利用回溯思路进行处理——>2.首先分析当前节点左右子树是否为null，为null说明到达叶子节点，当前节点已到最大深度——>3.然后进行递归左右子树——>4.得到最大深度之后进行回溯
总结就是在前序位置判断是否到达叶子节点并且depth++
// 记录最大深度
int res = 0;
// 记录遍历到的节点的深度
int depth = 0;
// 主函数
int maxDepth(TreeNode root) {
traverse(root);
return res;
}
// 二叉树遍历框架
void traverse(TreeNode root) {
if (root == null) {
return;
}
// 前序位置
depth++;
if (root.left == null && root.right == null) {
// 到达叶子节点，更新最大深度
res = Math.max(res, depth);
}
traverse(root.left);
traverse(root.right);
// 后序位置
depth--;
}
优化：1.后序位置进行操作——>2.遍历到最深的时候，求左右子树max最大深度+1=当前节点最大深度
// 定义：输入根节点，返回这棵二叉树的最大深度
int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
// 利用定义，计算左右子树的最大深度
int leftMax = maxDepth(root.left);
int rightMax = maxDepth(root.right);
// 整棵树的最大深度等于左右子树的最大深度取最大值，
// 然后再加上根节点自己
int res = Math.max(leftMax, rightMax) + 1;
return res;
}
二叉树的直径
思路：直接递归每个节点就完了——>1.前序位置求每个节点的最大深度并且更新最大直径——>2.递归每个节点
// 记录最大直径的长度
int maxDiameter = 0;
public int diameterOfBinaryTree(TreeNode root) {
// 对每个节点计算直径，求最大直径
traverse(root);
return maxDiameter;
}
// 遍历二叉树
void traverse(TreeNode root) {
if (root == null) {
return;
}
// 对每个节点计算直径
int leftMax = maxDepth(root.left);
int rightMax = maxDepth(root.right);
int myDiameter = leftMax + rightMax;
// 更新全局最大直径
maxDiameter = Math.max(maxDiameter, myDiameter);
traverse(root.left);
traverse(root.right);
}
// 计算二叉树的最大深度
int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
int leftMax = maxDepth(root.left);
int rightMax = maxDepth(root.right);
return 1 + Math.max(leftMax, rightMax);
}
优化：直接在后序进行操作——>1.base：叶子节点返回0——>2.进行递归得到叶子节点——>3.在后序位置计算最大直径并且进行更新——>4.然后子树最大深度+1=当前节点最大深度
// 记录最大直径的长度
int maxDiameter = 0;
public int diameterOfBinaryTree(TreeNode root) {
maxDepth(root);
return maxDiameter;
}
int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
int leftMax = maxDepth(root.left);
int rightMax = maxDepth(root.right);
// 后序位置，顺便计算最大直径
int myDiameter = leftMax + rightMax;
maxDiameter = Math.max(maxDiameter, myDiameter);
return 1 + Math.max(leftMax, rightMax);
}
前序后序总结
1.前序位置无法获取子树信息，所以只能让每个节点调用 maxDepth 函数去算子树的深度
2.把计算「直径」的逻辑放在后序位置，准确说应该是放在 maxDepth 的后序位置，因为 maxDepth 的后序位置是知道左右子树的最大深度的
翻转二叉树
思路：1.在前序位置进行操作——>2.将当前节点的左右子树进行交换——>3.然后进行递归
class Solution {
public TreeNode invertTree(TreeNode root) {
traverse(root);
return root;
}
void traverse(TreeNode root){
//1.base
if(root==null){
return;
}
//2.前序位置，交换
TreeNode temp=root.left;
root.left=root.right;
root.right=temp;
//3.递归其他节点
traverse(root.left);
traverse(root.right);
}
}填充每个节点的下一个右侧节点指针
116. 填充每个节点的下一个右侧节点指针 - 力扣（LeetCode）
思路：1.和前面一样，在前序位置进行操作——>2.base：左右子树为null，直接return——>3.前序位置，左右相连——>4.进行递归
class Solution {
public Node connect(Node root) {
//1.特殊情况
if(root==null) return null;
HelperConnect(root.left,root.right);
return root;
}
//原地修改二叉树节点之间的连接，传入两个节点，将其相连
public void HelperConnect(Node node1, Node node2) {
//1.base
if(node1==null||node2==null){
return;
}
//2.前序位置
node1.next=node2;
HelperConnect(node1.left,node1.right);
HelperConnect(node2.left,node2.right);
HelperConnect(node1.right,node2.left);
}
}填充每个节点的下一个右侧节点指针
116. 填充每个节点的下一个右侧节点指针 - 力扣（LeetCode）
思路：1.和前面一样，在前序位置进行操作——>2.base：左右子树为null，直接return——>3.前序位置，左右相连——>4.进行递归
class Solution {
public Node connect(Node root) {
//1.特殊情况
if(root==null) return null;
HelperConnect(root.left,root.right);
return root;
}
//原地修改二叉树节点之间的连接，传入两个节点，将其相连
public void HelperConnect(Node node1, Node node2) {
//1.base
if(node1==null||node2==null){
return;
}
//2.前序位置
node1.next=node2;
HelperConnect(node1.left,node1.right);
HelperConnect(node2.left,node2.right);
HelperConnect(node1.right,node2.left);
}
}将二叉树展开为链表
思路：1.要拉平链表——>2.我们进行递归到局部叶子节点，进行后序操作——>3.我们将左右子树保存，当前节点左子树置为空，然后将左子树移到当前节点的右子树上 ，然后对右子树进行遍历，到叶子节点，最后再将之前的right移到右子树上
// 定义：将以 root 为根的树拉平为链表
void flatten(TreeNode root) {
// base case
if (root == null) return;
// 利用定义，把左右子树拉平
flatten(root.left);
flatten(root.right);
/**** 后序遍历位置 ****/
// 1、左右子树已经被拉平成一条链表
TreeNode left = root.left;
TreeNode right = root.right;
// 2、将左子树作为右子树
root.left = null;
root.right = left;
// 3、将原先的右子树接到当前右子树的末端
TreeNode p = root;
while (p.right != null) {
p = p.right;
}
p.right = right;
}
最大二叉树
思路：1.首先得到根节点root——>2.然后对maxVal(root)的左边数组和右边数组进行递归构造作为root的左右子树
模板：
TreeNode constructMaximumBinaryTree([3,2,1,6,0,5]) {
// 找到数组中的最大值
TreeNode root = new TreeNode(6);
// 递归调用构造左右子树
root.left = constructMaximumBinaryTree([3,2,1]);
root.right = constructMaximumBinaryTree([0,5]);
return root;
}
遍历数组得到最大值并且记录索引——>然后进行递归左右子树——>base：越界就return null
public TreeNode constructMaximumBinaryTree(int[] nums) {
return build(0, nums.length - 1, nums);
}
TreeNode build(int start, int end, int[] nums) {
//1.base:start>end
if (start > end) return null;
//2.确定最大值并且确定它的位置
int index = -1, MAX_VALUE = Integer.MIN_VALUE;
for (int i = start; i <= end; i++) {
if (MAX_VALUE < nums[i]) {
MAX_VALUE = nums[i];
index = i;
}
}
//3.构造当前的根节点
TreeNode root=new TreeNode(MAX_VALUE);
//4.递归调用左右子树
root.left=build(start,index-1,nums);
root.right=build(index+1,end,nums);
return root;
}通过前序和中序遍历结果构造二叉树
前序遍历和中序遍历的结果有什么特点？
void traverse(TreeNode root) {
// 前序遍历
preorder.add(root.val);
traverse(root.left);
traverse(root.right);
}
void traverse(TreeNode root) {
traverse(root.left);
// 中序遍历
inorder.add(root.val);
traverse(root.right);
}
解决：
1.首先根据前序遍历得到根节点——>2.然后再在中序遍历进行查找得到中序遍历中的index——>3.进行递归
root.left=Helper(preorder,preStart+1,index-inStart+preStart,inorder,inStart,index-1);
root.right=Helper(preorder,preStart+index-inStart+1,preEnd,inorder,index+1,inEnd);class Solution {
/**
* 利用给定的前序中序排列得到二叉树
* 主要是利用前序位置进行操作——>在中序中找到根节点
* @param preorder
* @param inorder
* @return
*/
//1.利用map的键值对进行优化
HashMap<Integer, Integer> valToIndex = new HashMap<>();
public TreeNode buildTree(int[] preorder, int[] inorder) {
for (int i = 0; i < inorder.length; i++) {
valToIndex.put(inorder[i], i);
}
return Helper(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
}
private TreeNode Helper(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd) {
//1.base
if (preStart > preEnd) return null;
//2.确定root以及在中序root的位置
int rootVal = preorder[preStart];
// rootVal 在中序遍历数组中的索引
int index = valToIndex.get(rootVal);
TreeNode root = new TreeNode(rootVal);
//3.递归左右子树
root.left=Helper(preorder,preStart+1,index-inStart+preStart,inorder,inStart,index-1);
root.right=Helper(preorder,preStart+index-inStart+1,preEnd,inorder,index+1,inEnd);
return root;
}
}
本文含有隐藏内容，请 开通VIP 后查看