当前位置：网站首页>二叉树的类型、构建、遍历、操作
二叉树的类型、构建、遍历、操作
2022-08-02 13:06:00 【菜就要学习】
涉及到构造二叉树（普通二叉树、二叉搜索树），一定前序（中左右），都是先构造中节点。确定中间节点（数组中的最大值为跟节点=最大二叉树，中间位置的值为根节点=平衡二叉树，有序数组=搜索二叉树），划分左右区间作为左右子树，重复上述步骤。
求普通二叉树的属性，一般是后序，一般要通过递归函数的返回值做计算。
求二叉搜索树的属性，一定是中序 = 升序序列。
递归一般情况下效率更高，考虑 结束情况和正常情况时的条件和操作，和对应的返回值
目录
3、层序遍历BFS：借助队列来实现，队列先进先出，符合一层一层遍历的逻辑
4.反转二叉树：全部交换左右子节点，可以用层次遍历：由上至下，或深度优先遍历：由下至上
5.求树的节点数=左子树节点个数+右子树节点个数+1，或层次遍历统计
6.对称二叉树：后序遍历，用递归函数的返回值判断两个子树的内侧和外侧的节点是否对应相等（一个子树：左右中；另一个：右左中）
7.高度平衡二叉树：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
8. 构建二叉树，根据已知的遍历序列，用前/或序遍历找到根节点（当前序列的第一个/最后一个元素），分割中序遍历找到左右子树。
9.构建最大二叉树，根据一个不含重复元素的数组为中序遍历序列。（最大值为根节点，左右分别为左右子树）
10.合并二叉树：遍历，将两个树的节点对应位置值相加。(迭代法)
11.升序数组转换为一棵高度平衡二叉搜索树：数组构构成平衡树是默认数组中间位置取值作为节点元素
12.二叉搜索树转换为累加树：(右中左)遍历+累加,处理中间节点，递归：先找到最右侧的值，在依次返回结果。
13. 二叉树的深度 = 根节点到最远叶子节点的最长路径上的节点数。（递归效率更高）
14.二叉树的最小深度 = 从根节点到最近叶子节点的最短路径上的节点数量。
15.二叉树的所有根节点到叶子结点的路径：由根节点开始遍历，所以用前序遍历（中左右）
17. 树左下角的值 = 最后一层的第一个元素，层次遍历，（每次遍历完记录一下第一个值，直到栈为空，返回）
18.路径总和=该树中是否存在根节点到叶子节点的路径所有节点值相加
19.二叉搜索树是一个有序树：左小右大，中序遍历，查找某值/验证/求最值/求差值
20.二叉搜索树中的节点：插入、删除，都是根据操作更新左右节点，注意保证搜索树性质
21. 二叉树的最近公共祖先: 自底向上查找 (回溯 / 后序遍历)
22.二叉搜索树的最近公共祖先：搜索树有序（相当于自带方向） 从上到下遍历，cur节点是数值在[p, q]区间中则说明该节点cur就是最近公共祖先
1、二叉树类型：
只有度为0或2的节点：满二叉树（底层满，k层，2^k-1个节点）、完全二叉树（堆，底层左侧满）
二叉搜索树：有数值、有序：左子树上的节点值小于根节点，右子树上的所有节点大于根节点
平衡二叉搜索树：左右两个子树的高度差的绝对值不超过1，且左右子树为平衡二叉树
2、二叉树的存储方式：
顺序存储（数组，父节点的数组下标是 i，那么它的左孩子就是 i * 2 + 1，右孩子就是 i * 2 + 2）、链式存储（指针，节点元素+左右指针）
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;
}
}3、二叉树的遍历方式：深度、广度
- 深度优先遍历：先往深走，遇到叶子节点再往回走。可用递归方式或栈实现
- 前中后为访问根节点的顺序，均是 先左子树 后右子树
- 前序遍历（递归法，迭代法）中左右
- 中序遍历（递归法，迭代法）左中右
- 后序遍历（递归法，迭代法）左右中
- 前中后为访问根节点的顺序，均是 先左子树 后右子树
- 广度优先遍历：一层一层的去遍历。一般用队列实现，先进先出
- 层次遍历（迭代法）
1.递归遍历（三要素）-> 深度优先遍历DFS
每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中，然后递归返回的时候，从栈顶弹出上一次递归的各项参数。
确定递归函数的参数和返回值：
确定终止条件： 防止栈溢出
确定单层递归的逻辑： 确定每一层递归需要处理的信息。
class Solution {
public List<Integer> orderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
preOrder(root,res);
//postOrder(root,res);
return res;
}
//深度优先遍历：前序遍历
public void preOrder(TreeNode root, List<Integer> res){
if(root == null){
return;
}
res.add(root.val);
preOrder(root.left,res);
preOrder(root.right,res);
}
//深度优先遍历：后序遍历
public void postOrder(TreeNode root, List<Integer> res){
if(root == null){
return;
}
postOrder(root.left,res);
postOrder(root.right,res);
res.add(root.val);
}
/深度优先遍历：中序遍历
public void inOrder(TreeNode root, List<Integer> res){
if(root == null) return;
inOrder(root.left,res);
res.add(root.val);
inOrder(root.right,res);
}
}2.迭代遍历（借助堆）-》深度优先遍历
前序遍历是中左右，每次先处理的是中间节点，那么各节点入栈顺序：中右左。
中序遍历，就需要借用指针的遍历来帮助访问节点，栈则用来处理节点上的元素。
后序遍历，只需要调整一下先序遍历的代码顺序，就变成中右左的遍历顺序，然后在反转result数组——————(均以最小子树为例进行思考）
统一处理方式：将访问的节点直接加入到栈中，但如果是处理的节点则后面放入一个空节点， 这样只有空节点弹出的时候，才将下一个节点放进结果集。
// 前序遍历顺序：中-左-右，入栈顺序：中-右-左
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null){
return result;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()){
TreeNode node = stack.pop(); //当前节点作为根节点，出栈
result.add(node.val);
if (node.right != null){
stack.push(node.right);//当前根节点的右子树入栈
}
if (node.left != null){
stack.push(node.left);//当前根节点的左子树入栈
}
}
return result;
}
}
// 中序遍历顺序: 左-中-右 入栈顺序： 左-右
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null){
return result;
}
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root; //指针，用来遍历节点
while (cur != null || !stack.isEmpty()){
if (cur != null){ //当前那节点不为空，作为根节点入栈，访问他的左子树
stack.push(cur);
cur = cur.left;
}else{
//当前节点为空，表示左子树访问结束，
//但栈中还有节点即各级根节点，则外侧根节点出栈，访问他的右子树
cur = stack.pop();
result.add(cur.val);
cur = cur.right;
}
}
return result;
}
}
// 后序遍历顺序 左-右-中 入栈顺序：中-左-右 出栈顺序：中-右-左， 最后翻转结果
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null){
return result;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()){
TreeNode node = stack.pop();
result.add(node.val);
if (node.left != null){
stack.push(node.left);
}
if (node.right != null){
stack.push(node.right);
}
}
Collections.reverse(result);
return result;
}
}//统一的迭代法：深度优先遍历
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
//首先判断根节点是否为空，不空入栈，空则返回结果null，
if(root != null){
stack.push(root);
}
while(! stack.isEmpty()){
// 1.读取栈顶数据
TreeNode cur = stack.pop();
if(cur != null){
//节点不为空，为有效数据，按照遍历顺序的反序存入栈中，
//当前节点入栈后，入栈一个空节点作为标记（表示其下一数据节点已经访问过左右子树了）
//前序遍历，中左右，入栈顺序：右左中
if(cur.right != null){stack.push(cur.right);}
if(cur.left != null){stack.push(cur.left);}
stack.push(cur);
stack.push(null);
//中序遍历，左中右，入栈顺序：右中左
if(cur.right != null){stack.push(cur.right);}
stack.push(cur);
stack.push(null);
if(cur.left != null){stack.push(cur.left);}
//后序遍历，左右中，入栈顺序：中右左
stack.push(cur);
stack.push(null);
if(cur.right != null){stack.push(cur.right);}
if(cur.left != null){stack.push(cur.left);}
}else{
//节点为空，说明其下一数据节点已经处理过，可以存入结果中
cur = stack.pop();
res.add(cur.val);
}
}
return res;
}
}3、层序遍历BFS：借助队列来实现，队列先进先出，符合一层一层遍历的逻辑
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
//注意返回值类型，每一行数据为一个list
List<List<Integer>> res = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
if(root != null){
queue.offer(root);
}
while(!queue.isEmpty()){
//一层一层遍历，每次遍历完队中只有下一层的数据，当前层的数据添加到当前List中
List<Integer> temp = new ArrayList<>();
int size = queue.size();
for(int i = 0; i<size; i++){
//每次出队（保存）一个节点，就将该节点的左右子树节点入队
TreeNode cur = queue.poll();
temp.add(cur.val);
if(cur.left != null) queue.add(cur.left);
if(cur.right != null) queue.add(cur.right);
}
//将该层节点的遍历添加到总遍历结果中
res.add(temp);
}
return res;
}
}- 107.二叉树的层次遍历（从下到上输出）：将结果表创建为LinkedList,将每层的遍历结果添加在表头，即：res.add(0,temp)
- 199.二叉树的右视图：层次遍历，只将每层最后一个元素（即该层的第size-1个元素）添加到结果表中,即：if(i == size-1){res.add(cur.val);}
- 637.二叉树的层平均值：层次遍历，每层遍历时求和算平均值，保存到结果中
- 429.N叉树的层序遍历：在每层遍历节点时，将每个节点的子节点存入队列中（遍历子节点）
for (Node child : cur.children) { queue.offer(child);}
- 515.在每个树行中找最大值：只保留每层的最大值，存入结果表
- 116.完美二叉树填充每个节点的下一个右侧节点指针：将队列中去除的元素next指向现在队头元素O(N)，或者，根据父节点的连接设置：head.left.next = head.right;//同一父节点，左节点的next=右节点， if (head.next != null) {head.right.next = head.next.left; }//不同父节点，右节点的next=父节点的next的左节点O(1)
- 117.任意二叉树填充每个节点的下一个右侧节点指针II：不断地根据父类找右侧存在的第一个节点
class Solution { public Node connect(Node root) { if(root==null) return root; if(root.left!=null && root.right!=null){ root.left.next=root.right; } if(root.left!=null && root.right==null){ root.left.next=getNext(root.next); } if(root.right!=null) root.right.next=getNext(root.next); connect(root.right); connect(root.left); return root; } public Node getNext(Node root){ if(root==null) return null; if(root.left!=null) return root.left; if(root.right!=null) return root.right; if(root.next!=null) return getNext(root.next); return null; } }- 104.二叉树的最大深度：递归（如下），或层次遍历，每一层遍历结束层数加1
public int maxDepth(TreeNode root) { return root == null ? 0 : Math.max(maxDepth(root.left), maxDepth(root.right)) + 1; } - 111.二叉树的最小深度：层次遍历，找到叶子结点即返回深度 或 递归：深度优先搜索，遍历整棵树，记录最小深度。
- （与层次有关的问题，可用层次遍历解决O(n)，也可用深度优先遍历+map表记录深度和数值O(H)）
4.反转二叉树：全部交换左右子节点，可以用层次遍历：由上至下，或深度优先遍历：由下至上
//层次遍历
// class Solution {
// public TreeNode invertTree(TreeNode root) {
// Queue<TreeNode> queue = new LinkedList<>();
// if(root != null){
// queue.offer(root);
// }
// while(!queue.isEmpty()){
// int size = queue.size();
// for(int i = 0; i < size; i++){
// TreeNode cur = queue.poll();
// swap(cur);
// if(cur.left != null) queue.offer(cur.left);
// if(cur.right != null) queue.offer(cur.right);
// }
// }
// return root;
// }
// public void swap(TreeNode cur){ //要传输根节点
// TreeNode temp = cur.left;
// cur.left = cur.right;
// cur.right = temp;
// }
// }
//深度遍历，迭代
class Solution {
public TreeNode invertTree(TreeNode root) {
if(root == null){
return null;
}
//先完成左右子树内的交换
invertTree(root.left);
invertTree(root.right);
//在交换根节点的左右子节点
swap(root);
return root;
}
public void swap(TreeNode cur){ //要传输根节点
TreeNode temp = cur.left;
cur.left = cur.right;
cur.right = temp;
}
}5.求树的节点数=左子树节点个数+右子树节点个数+1，或层次遍历统计
递归法：
- 结束情况；左右子树为空，返回0+1；
- 正常情况：左子树节点个数+右子树节点个数+1；
迭代法：层次遍历，每遇到一个节点+1，直到队列为空
若为完全二叉树（只有最后一层可能不满，满则为满二叉树），
- 树的最左侧和最右侧节点的深度相同时，该树为满二叉树，节点数=2^(树的深度)-1；
- 完全二叉树：递归左右孩子，知道左右孩子为满二叉树时按照上述计算，向上返回。
//递归法，求普通二叉树节点数
// class Solution {
// public int countNodes(TreeNode root) {
// if(root == null) return 0;
// return 1+countNodes(root.left)+countNodes(root.right);
// }
// }
//递归法：求完全二叉树节点数
class Solution {
public int countNodes(TreeNode root) {
if(root == null) return 0;
TreeNode left = root.left;
TreeNode right = root.right;
int leftDepth = 0,rightDepth = 0;
while(left != null){
left = left.left;
leftDepth++;
}
while(right != null){
right = right.right;
rightDepth++;
}
if(leftDepth == rightDepth){
return (2<<leftDepth) - 1;
}
return countNodes(root.left)+countNodes(root.right)+1;
}
}4、二叉树类型验证、构建
6.对称二叉树：后序遍历，用递归函数的返回值判断两个子树的内侧和外侧的节点是否对应相等（一个子树：左右中；另一个：右左中）
递归法：如果需要遍历整棵树，递归函数就不能有返回值。如果需要遍历某一条固定路线，递归函数就一定要有返回值！
- 首先考虑结束时的情况：即左右子树中有空子树：其中一个为空不队称，都为空对称。
- 在考虑正常情况：左右子树均不为空，比较对应的节点值，全相同返回true比较上一级，不相同则结束即不对称false
迭代法：队列（先入先出）或堆栈（前入后出）均可，（成对出入）
- 首先将当前节点的左右子节点入队，判断是否相等，不相等则不对称，结束false
- 相等则将当前的左右节点出栈，再按照左节点的左孩子，右节点右孩子，左节点右孩子，右节点左孩子入栈（即先外侧入栈在内侧）。
- 结束时的情况：即左右节点中有空子树：其中一个为空不队称，都为空对称；或左右节点值不相等
//递归方法
// class Solution {
// public boolean isSymmetric(TreeNode root) {
// if(root == null){
// return true;
// }
// return compare(root.left, root.right);
// }
// public boolean compare(TreeNode left, TreeNode right){
// if(left == null && right == null) return true;
// if(left == null || right == null) return false;
// if(left.val != right.val) return false;
// return compare(left.left,right.right) && compare(left.right,right.left);
// }
// }
// 迭代法
class Solution {
public boolean isSymmetric(TreeNode root) {
if(root == null){
return true;
}
Queue<TreeNode> que = new LinkedList<>();
que.offer(root.left);
que.offer(root.right);
while(!que.isEmpty()){
TreeNode left = que.poll();
TreeNode right = que.poll();
if(left == null && right == null) continue;
if(left == null || right == null) return false;
if( left.val != right.val) return false;
que.offer(left.left);
que.offer(right.right);
que.offer(left.right);
que.offer(right.left);
}
return true;
}
}7.高度平衡二叉树：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
- 二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数。
- 二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数。无法用层序遍历求
递归法: 求子树高度
- 结束情况：遇到空节点，return 0；
- 正常情况：求左右子树的高度，计算差值 ，
- 左右子树中存在子树高度=-1，表示该树应经不满足高度平衡，return -1
- 差值>1 return -1（表示不高度平衡）,
- 差值<=1 return 节点高度，即1+子树高度中的较大值。
class Solution {
public boolean isBalanced(TreeNode root) {
return getHeight(root) == -1? false:true;
}
public int getHeight(TreeNode root){
if(root == null) return 0;
int leftH = getHeight(root.left);
int rightH = getHeight(root.right);
if(leftH == -1 || rightH == -1) return -1;
if(Math.abs(leftH-rightH) > 1) return -1;
return 1+Math.max(leftH, rightH);
}
}8. 构建二叉树，根据已知的遍历序列，用前/或序遍历找到根节点（当前序列的第一个/最后一个元素），分割中序遍历找到左右子树。
106. 从中序与后序遍历序列构造二叉树 左中右 左右中
105. 从前序与中序遍历序列构造二叉树 中左右 左中右
- (画图更容易理解)，确定子树在序列中的位置（序列区间，闭还是开？）
- 分割时候，坚持区间不变量原则，左闭右开，或者左闭又闭。去除原序列中的已用节点
- 通过下标索引直接在原数组上操作，这样可以节约时间和空间上的开销。
- 在中序序列中 需要多次查找 根节点所在位置，可用map映射提高查找效率
//从中序与后序遍历序列构造二叉树
class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
return buildNode(inorder,0,inorder.length-1,postorder,0,postorder.length-1);
}
//区间：左闭右闭
public TreeNode buildNode(int[] inorder, int inbegin, int inend, int[] postorder, int postbegin, int postend) {
if(inbegin > inend) return null;//当前序列为空
TreeNode root = new TreeNode();
root.val = postorder[postend];
int leftL = 0;
int i = inbegin;
for(; i <= inend; i++){
if(inorder[i] == root.val){
leftL = i-inbegin;
break;
}
}
//注意区间范围，左闭右闭
root.left = buildNode(inorder,inbegin,inbegin+leftL-1,postorder,postbegin,postbegin+leftL-1);
root.right = buildNode(inorder,i+1,inend,postorder,postbegin+leftL,postend-1);
return root;
}
}
//从前序与中序遍历序列构造二叉树
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
//以中序遍历序列左分割，需要多次查找，做map映射
Map<Integer,Integer> map = new HashMap<>();
for(int i = 0; i < inorder.length; i++){
map.put(inorder[i],i);
}
return buildNode(map,0,inorder.length-1,preorder,0,preorder.length-1);
}
//区间：左闭右闭
public TreeNode buildNode(Map inorder, int inbegin, int inend, int[] preorder, int prebegin, int preend) {
if(inbegin > inend) return null;//当前序列为空
TreeNode root = new TreeNode();
root.val = preorder[prebegin]; //区别，前序遍历取第一个，后序遍历取最后一个
int i = (Integer) inorder.get(root.val);
int leftL = i-inbegin;
//注意区间范围，左闭右闭, 区别 前序遍历去除第一个，后序遍历去除最后一个
root.left = buildNode(inorder,inbegin,inbegin+leftL-1,preorder,prebegin+1,prebegin+leftL-1);
root.right = buildNode(inorder,i+1,inend,preorder,prebegin+1+leftL,preend);
return root;
}
}9.构建最大二叉树，根据一个不含重复元素的数组为中序遍历序列。（最大值为根节点，左右分别为左右子树）
class Solution {
public TreeNode constructMaximumBinaryTree(int[] nums) {
return constructNode(nums,0,nums.length-1);
}
// 闭区间
public TreeNode constructNode(int[] nums, int begin, int end) {
if(begin > end) return null;
int maxindex = begin;
int max = nums[begin];
for(int i = begin+1; i <= end; i++){
if(nums[i] > max){
max = nums[i];
maxindex = i;
}
}
TreeNode root = new TreeNode(max);
root.left = constructNode(nums,begin,maxindex-1);
root.right = constructNode(nums,maxindex+1,end);
return root;
}
}10.合并二叉树：遍历，将两个树的节点对应位置值相加。(迭代法)
- 遍历树的每一个节点。
- 两个树的节点对应位置，存在元素，相加后作为新值,在确定左右子树的节点；
- 只存在一个元素（即另一个为null），不为 NULL 的节点将直接作为新二叉树的节点。
class Solution {
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
if(root1 == null) return root2;
if(root2 == null) return root1;
root1.val += root2.val;//将结果保存在root1中
root1.left = mergeTrees(root1.left,root2.left);
root1.right = mergeTrees(root1.right,root2.right);
return root1;
}
}11.升序数组转换为一棵高度平衡二叉搜索树：数组构构成平衡树是默认数组中间位置取值作为节点元素
108. 将有序数组转换为二叉搜索树：高度平衡二叉树：指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
- 本质就是寻找数组的分割点，分割点作为当前节点，然后递归左区间和右区间。
- 平衡：以数组的中间元素为根节点，（偶数个元素，取左或右都可以）int mid = left + ((right - left) / 2); 再递归遍历左右区间，确定左右子节点的值
- 搜素：升序数组
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return travesal(nums, 0, nums.length-1);//闭区间 ,用上下界划分区间
}
public TreeNode travesal(int nums[], int low, int high){
if(high < low) return null;
int mid = low + (high-low)/2;
TreeNode cur = new TreeNode(nums[mid]);
cur.left = travesal(nums,low, mid-1);
cur.right = travesal(nums,mid+1,high);
return cur;
}
}12.二叉搜索树转换为累加树：(右中左)遍历+累加,处理中间节点，递归：先找到最右侧的值，在依次返回结果。
累加树（Greater Sum Tree）：使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和
//递归法：推荐
// class Solution {
// int sum = 0;
// public TreeNode convertBST(TreeNode root) {
// travesal(root);
// return root;
// }
// public void travesal(TreeNode cur){
// if(cur == null) return;
// travesal(cur.right);//先从右侧开始累加
// sum += cur.val;
// cur.val = sum;
// travesal(cur.left);
// }
// }
//迭代法: 深度遍历的统一写法
class Solution {
public TreeNode convertBST(TreeNode root) {
if(root == null) return null;
Stack<TreeNode> stack = new Stack<>();//先存的后出去
stack.push(root);
TreeNode cur = root;
int pre = 0;
while(!stack.isEmpty()){
TreeNode node = stack.pop();//弹出当前节点，按遍历顺序的反序存放：右中左-》左中右
if(node != null){//为处理过的元素
if(node.left != null) stack.push(node.left);
stack.push(node);
stack.push(null);//标签上一个节点node已经处理左右节点过了，下次遇到可以直接处理
if(node.right != null) stack.push(node.right);
}else{
node = stack.pop();
node.val += pre;
pre = node.val;
}
}
return root;
}
}5、 二叉树的路径相关
13. 二叉树的深度 = 根节点到最远叶子节点的最长路径上的节点数。（递归效率更高）
，104. 二叉树的最大深度，559. N 叉树的最大深度（方法相同，递归遍历每一个子节点）
递归法：使用前序遍历（中左右）求的就是深度，使用后序遍历（左右中）求的是高度。根节点的高度就是二叉树的最大深度。
- 结束条件：当前节点的为空，return 0；
- 正常情况：当前节点不为空，计算它左右子树的深度，取较大值，return当前深度 即子树深度+1；
迭代法：使用层次遍历,每层深度+1；
//递归法
// class Solution {
// public int maxDepth(TreeNode root) {
// if(root == null) return 0;
// int leftDepth = maxDepth(root.left);
// int rightDepth = maxDepth(root.right);
// return 1+Math.max(leftDepth, rightDepth);
// }
// }
//迭代法
class Solution {
public int maxDepth(TreeNode root) {
if(root == null) return 0;
Queue<TreeNode> que = new LinkedList<>();
int depth = 0;
que.offer(root);
while(!que.isEmpty()){
int size = que.size();
depth++;
while(size>0){
TreeNode cur = que.poll();
if(cur.left != null) que.offer(cur.left);
if(cur.right != null) que.offer(cur.right);
size--;
}
}
return depth;
}
}14.二叉树的最小深度 = 从根节点到最近叶子节点的最短路径上的节点数量。
111. 二叉树的最小深度（迭代法：层次遍历效率更高）
递归法：
- 结束情况：找到左右孩子均为空的节点，结束 即return 0+1
- 正常情况：
- 左右子树均不为空，取较小值+1
- 左子树为空，右子树不空，取右子树深度+1 (子树为空即深度=0)
- 右子树为空，左子树不空，取左子树深度+1
迭代法：层次遍历，遇到左右子树为空的节点结束，返回当前深度；
//递归法
// class Solution {
// public int minDepth(TreeNode root) {
// if(root == null) return 0;
// int leftDepth = minDepth(root.left);
// int rightDepth = minDepth(root.right);
// if(leftDepth == 0 || rightDepth == 0){
// return 1+leftDepth+rightDepth;
// }
// return 1+Math.min(leftDepth,rightDepth);
// }
// }
//迭代法
class Solution {
public int minDepth(TreeNode root) {
if(root == null) return 0;
Queue<TreeNode> que = new LinkedList<>();
que.offer(root);
int depth = 0;
while(!que.isEmpty()){
depth++;
int size = que.size();
while(size>0){
TreeNode cur = que.poll();
if(cur.left == null && cur.right == null){
return depth;
}
if(cur.left != null) que.offer(cur.left);
if(cur.right != null) que.offer(cur.right);
size--;
}
}
return depth;
}
}15.二叉树的所有根节点到叶子结点的路径：由根节点开始遍历，所以用前序遍历（中左右）
递归+回溯：（效率更高）
回溯和递归是一一对应的，有一个递归，就要有一个回溯 （回溯即当前函数调用完，对应的参数不曾改变，可以在调用的函数内部做改变，或者函数调用完恢复数据）
- 当前路径结束条件：该节点的左右孩子为null，将当前路径路径中并保存到res中，结束。
- 正常情况：
- 判断根节点是否为空 （只有root需要判断），不为空就在路径中添加该节点值。
- 先判断左子树是否为空，不为空，路径中保存左孩子节点，直到遍历结束，回溯到上一节点；
- 在判断右子树是都为空，不为空，路径中保存右孩子节点，直到遍历结束，回溯到上一节点；
- 按照 中左右的顺序依次判断
迭代法：回溯（后进先出）——》堆栈。前序遍历的存放顺序：中右左，将节点和路径同时入栈
- 根节点不为空，入栈 （占用了更多的空间，操作更多）
- 判断左右子节点是否全为空，为空，则保存路径
- 右子节点不为空，节点值+节点路径(到当前节点的路径) 入栈，
- 左节点不为空，节点值+节点路径 入栈，
// //递归+回溯
// class Solution {
// public List<String> binaryTreePaths(TreeNode root) {
// if(root == null) return null;
// List<String> res = new ArrayList<>();
// List<Integer> path = new ArrayList<>();
// travesal(root,path,res);
// return res;
// }
// public void travesal(TreeNode root,List<Integer> path, List<String>res){
// path.add(root.val);
// if(root.left == null && root.right == null){
// StringBuffer paths = new StringBuffer(3*path.size());
// for(int i = 0; i < path.size()-1; i++){
// paths.append(path.get(i)).append("->");
// }
// paths.append(path.get(path.size()-1));
// res.add(paths.toString());
// return;
// }
// if(root.left != null){
// travesal(root.left,path,res);
// path.remove(path.size()-1);
// }
// if(root.right != null){
// travesal(root.right,path,res);
// path.remove(path.size()-1);
// }
// }
// }
//迭代法
class Solution {
public List<String> binaryTreePaths(TreeNode root) {
if(root == null) return null;
List<String> res = new ArrayList<>();
Stack<Object> stack = new Stack<Object>();
stack.push(root);
stack.push(root.val + "");
while (!stack.isEmpty()) {
// 节点和路径同时出栈
String path = (String) stack.pop();
TreeNode cur = (TreeNode) stack.pop();
if(cur.left == null && cur.right == null){
res.add(path);
}
if(cur.right != null){
stack.push(cur.right);
stack.push(path+"->"+cur.right.val);
}
if(cur.left != null){
stack.push(cur.left);
stack.push(path+"->"+cur.left.val);
}
}
return res;
}
}16. 左叶子之和：左节点且没有左右孩子的节点值之和
递归法：
- 结束情况：节点为空，return 0
- 单层逻辑：
- 判断是否为左叶子节点,是则保存节点值，不是则为0。
- 计算左右子树的左叶子之和，如果是空子树，和为0；
- 当前节点的左叶子之和 = 当前左叶子节点值+左子树之和+右子树之和（空或不是都为0.不影响结果）
迭代法：存入栈 + 节点遍历 + 条件判断
// 递归法
class Solution {
public int sumOfLeftLeaves(TreeNode root) {
if(root == null) return 0;
int val = 0;
//判断是否为左叶子节点,是则保存节点值，不是则为0
if(root.left != null && root.left.left == null && root.left.right == null){
val = root.left.val;
}
return val + sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);
}
}
//迭代法
// class Solution {
// public int sumOfLeftLeaves(TreeNode root) {
// if(root == null) return 0;
// int val = 0;
// Queue<TreeNode> que = new LinkedList<>();
// que.offer(root);
// while(!que.isEmpty()){
// TreeNode cur = que.poll();
// //判断是否为左叶子节点,是则保存节点值，不是则为0
// if(cur.left != null && cur.left.left == null && cur.left.right == null){
// val += cur.left.val;
// }
// if(cur.left != null) que.offer(cur.left);
// if(cur.right != null) que.offer(cur.right);
// }
// return val;
// }
// }17. 树左下角的值 = 最后一层的第一个元素，层次遍历，（每次遍历完记录一下第一个值，直到栈为空，返回）
class Solution {
public int findBottomLeftValue(TreeNode root) {
if(root == null) return -1;
int res = -1;
Queue<TreeNode> que = new LinkedList<>();
que.offer(root);
while(!que.isEmpty()){
int size = que.size();
for(int i=0; i<size; i++){
TreeNode cur = que.poll();
if(i == 0) res = cur.val;
if(cur.left != null) que.offer(cur.left);
if(cur.right != null) que.offer(cur.right);
}
}
return res;
}
}18.路径总和=该树中是否存在根节点到叶子节点的路径所有节点值相加
112. 路径总和寻找存在等于目标和的路径 112. 路径总和 判断是否存在,113. 路径总和 II保存所有满足条件的路径
前序遍历（中左右）+递归+回溯
- 结束情况：
- 叶子结点（左右孩子为null）+ 计数器正好减为0即count = 0 ,return true,否则false
- (不能用该条件判断，因为题目中节点值和目标值都可能为负，当前条件不成立，只有都为正时才成立)当前节点不是叶子结点，但count <= 0, return false;
- 正常情况：
- 当前节点不是null，计数器-节点值
- 先访问左子树,访问结束后回溯一个节点，
- 在访问右子树，访问结束后回溯一个节点。
- 返回值：boolean 参数：根节点，计数器（让计数器初值为目标和）。
迭代法：堆.栈中保存成对保存 当前节点 和 包含当前节点的路径和 ，在遍历的过程中比较。
// 递归法+回溯（返回上一级时targetSum为当前已有路径和，不包含当前节点）
class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
if(root == null) return false;
targetSum -= root.val;
if(root.left == null && root.right == null){
return targetSum == 0;
}
return hasPathSum(root.left,targetSum)||hasPathSum(root.right,targetSum);
}
}
// 迭代法（队列、栈）
// class Solution {
// public boolean hasPathSum(TreeNode root, int targetSum) {
// if(root == null) return false;
// Queue<Object> que = new LinkedList<>();
// que.offer(root);
// que.offer(root.val);
// while(!que.isEmpty()){
// TreeNode cur = (TreeNode)que.poll();
// Integer sum = (Integer)que.poll();
// if(cur.left == null && cur.right == null && sum == targetSum){
// return true;
// }
// if(cur.left != null){
// que.offer(cur.left);
// que.offer(sum+cur.left.val);
// }
// if(cur.right != null){
// que.offer(cur.right);
// que.offer(sum+cur.right.val);
// }
// }
// return false;
// }
// }//找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
class Solution {
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
findPath(root,targetSum,path,res);
return res;
}
public void findPath(TreeNode root, int targetSum, List<Integer> path, List<List<Integer>> res){
if(root == null) return;
path.add(root.val);
targetSum -= root.val;
if(root.left == null && root.right == null && targetSum == 0){
res.add(new ArrayList<>(path)); //出错点.需要将path的全部数据作为一个整体交给res
}
findPath(root.left,targetSum,path,res); //targetSum自动回溯
findPath(root.right,targetSum,path,res);
path.remove(path.size()-1);//手动回溯， path数组链表，不能自动回溯
}
}6、二叉搜索树的相关操作
19.二叉搜索树是一个有序树：左小右大，中序遍历，查找某值/验证/求最值/求差值
- 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
- 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；（不能单纯的比较子节点与中间节点）
- 它的左、右子树也分别为二叉搜索树
- 最值：二叉树中通过两个前后指针作比较，不要定义一个全局遍历，然后遍历序列更新全局变量求最值。因为最值可能就是int 或者 longlong的最小值。
- 验证：有上下限(划定当前节点数值的有效范围)
- 左子树：左侧节点比根节点小就可以，右侧节点不仅要比根节点大，但是比上一个根节点小
- 右子树：右侧节点比根节点大就可以，左侧节点不仅要比根节点小，但是比上一个根节点大
- 计算二叉搜索树中任意两节点的差的绝对值的最小值:530. 二叉搜索树的最小绝对差
- 二叉搜索树有序数，中序遍历后为有序数组，比较序列中前后两指的差值和当前差值， 取较小的。
- 在有序数组求任意两数最小值差等价于相邻两数的最小值差。
寻找出现频率最高的元素。501. 二叉搜索树中的众数
通用方法（暴力遍历）：遍历整棵树，map统计每个元素的出现次数，对map进行排序，取最高值（含相同最高值）
针对二叉搜索树：中序遍历后，相同元素一定相邻，找相同元素相邻数目最多的
class Solution {
// 在二叉搜索树中查找
public TreeNode searchBST(TreeNode root, int val) {
if(root == null || root.val == val) return root;
if(val < root.val){
return searchBST(root.left,val);
} else{
return searchBST(root.right,val);
}
}
// 在普通二叉树中查找
public TreeNode searchBST(TreeNode root, int val) {
if(root == null || root.val == val) return root;
TreeNode left = searchBST(root.left,val);
//判断有没有查找到,找到了就返回结果
if(left != null){
return left;
}
return searchBST(root.right,val);
}
//验证
public boolean isValidBST(TreeNode root) {
return isValid(root, Long.MIN_VALUE, Long.MAX_VALUE);//以最大最小值作为初始上下界
}
public boolean isValid(TreeNode root, long lower, long upper) {
if(root == null) return true;//空树也是二叉搜索树
if(root.val <= lower || root.val >= upper) return false;//不满足数值范围
return isValid(root.left,lower,root.val) && isValid(root.right,root.val,upper);
}
// 二叉搜索树的最小绝对差
TreeNode pre = null;
int res = Integer.MAX_VALUE;
public int getMinimumDifference(TreeNode root) {
travesal(root);
return res;
}
//中序遍历：二叉搜索树-》有序序列（小到大）
public void travesal(TreeNode cur){
if(cur == null) return;
travesal(cur.left);//找到当前的最小值
if(pre != null) {
res = Math.min(res,cur.val-pre.val);//计算当前值与前一个值的差
}
pre = cur;//比较完后，指针后移
travesal(cur.right);
}
}
//返回 BST 中的所有 众数（即，出现频率最高的元素）。
class Solution {
List<Integer> resList = new ArrayList<>();
TreeNode pre = null;//存储前一个节点
int count = 0;//相同值的节点计数
int maxCount = 0;//相同元素个数的最大值
public int[] findMode(TreeNode root) {
if(root == null) return null;
travesal(root);
int[] res = new int[resList.size()];//数组最开始无法确定长度，先创建一个临时存储的List
for(int i=0; i<resList.size(); i++){
res[i] = resList.get(i);
}
return res;
}
//中序遍历，找相邻数目中相同元素最多的,所以需要存储前一个节点的值pre.
//二叉搜索树，中序遍历后，相同元素一定相邻。
public void travesal(TreeNode cur){
if(cur == null) return;
travesal(cur.left);
if(pre == null){//遍历的第一个元素
count = 1;
}else if(pre.val == cur.val){
count++;
}else{//当前数值不相同，重新计数
count = 1;
}
pre = cur;
if(count > maxCount){
maxCount = count;
resList.clear();
resList.add(cur.val);
}else if(count == maxCount){
resList.add(cur.val);
}
travesal(cur.right);
}
}20.二叉搜索树中的节点：插入、删除，都是根据操作更新左右节点，注意保证搜索树性质
701. 二叉搜索树中的插入操作：寻找满足搜索树条件且为空的位置插入值，或者更新插入值后的节点。
- 按照搜索树的节点分布规则，寻找等于该值的节点cur，并记录其前一个节点pre。
- 节点删除要保证搜索树的性质，
- 方式一：当前节点变为它的右子节点，左子节点移到cur右子树的最左侧的节点的左孩子
- 方式二：当前节点变为它的左子节点，右子节点移到cur左子树的最右侧的节点的右孩子
669. 修剪二叉搜索树: 使得所有节点的值在[L, R]中 (R>=L)
- 当前节点值cur.val > R,符合条件的节点只能在左子树中，找到val<=R 的节点，返回，找到空，则返回null.
- 当前节点值cur.val < L,全在左子树中，找到val>=L 的节点，返回
- 当前节点值cur.val 在[L, R]中,左右分别找到不满足[L,R]的初始节点删除。注意左子树的右孩子、右子树的左孩子的值，若该值满足条件替换其父节点。
// //递归：无返回值的
// class Solution {
// public TreeNode insertIntoBST(TreeNode root, int val) {
// if(root == null) return new TreeNode(val);
// insert(root,val);
// return root;
// }
// public void insert(TreeNode root,int val){
// //为空，说明找到了插入的位置
// if(root.val > val) {
// if(root.left == null){
// root.left = new TreeNode(val);
// }else{
// insert(root.left,val);
// }
// }
// if(root.val < val) {
// if(root.right == null){
// root.right = new TreeNode(val);
// }else{
// insert(root.right,val);
// }
// }
// }
// }
// 递归：有返回值，根据返回值完成节点赋值
class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
if(root == null) return new TreeNode(val);
if(root.val > val) root.left = insertIntoBST(root.left,val);//插入值在左侧，更新 左子树节点
if(root.val < val) root.right = insertIntoBST(root.right,val);//插入值在右侧，更新 右子树节点
return root;
}
}
//删除二叉搜索树中值为key的节点
class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
if(root == null) return null;//没找到
if(root.val == key) {
if(root.right == null) return root.left;
if(root.left == null) return root.right;
//找右子树的最小值位置
TreeNode cur = root.right;
while(cur.left != null){
cur = cur.left;
}
cur.left = root.left;
return root.right;
}
//更新操作后的节点
if(root.val > key) root.left = deleteNode(root.left,key);
if(root.val < key) root.right = deleteNode(root.right,key);
return root;
}
}
//修剪二叉搜索树，使得所有节点的值在[low, high]中
//递归法
class Solution {
public TreeNode trimBST(TreeNode root, int low, int high) {
if(root == null) return null;
// 寻找符合区间[low, high]的节点
if(root.val > high) return trimBST(root.left,low,high);//要么返回左侧满足条件的孩子，要么返回空
if(root.val < low) return trimBST(root.right,low,high);
// root.val满足条件，给root接入符合条件的孩子
root.left = trimBST(root.left,low,high);
root.right = trimBST(root.right,low,high);
return root;
}
}
//迭代法
class Solution {
public TreeNode trimBST(TreeNode root, int low, int high) {
if(root == null) return null;
while(root != null && (root.val < low || root.val > high)){
if(root.val < low) {root = root.right; continue;}
if(root.val > high) {root = root.left;continue;}
}
//当前root满足条件范围，将root的左右两侧不满足条件的去除
TreeNode cur = root;
while(cur != null){
//左节点不满足条件式，判断左节点的孩子
while(cur.left != null && cur.left.val < low){
cur.left = cur.left.right;
}
cur = cur.left;
}
cur = root;
while(cur != null){
while(cur.right != null && cur.right.val > high){
cur.right = cur.right.left;
}
cur = cur.right;
}
return root;
}
}7、两节点的最近公共祖先
21. 二叉树的最近公共祖先: 自底向上查找 (回溯 / 后序遍历)
236. 二叉树的最近公共祖先找到该树中两个指定节点的最近公共祖先。
- 结束情况：找到p/q节点,返回该节点，或当前节点为null，没找到，返回null
- 正常情况：
- 分别遍历当前节点的左右子树，判断是否存在寻找到的节点，后序遍历（节点中存放的是最近的公共祖先）
- 都不为空，当前节点为公共节点，都为空，返回空
- 一侧为空，一侧不为空，返回不为空的节点
- 返回值为寻找的节点本身，或者二者的最近公共祖先、或null
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == p || root == q|| root == null) return root;
TreeNode left = lowestCommonAncestor(root.left,p,q);
TreeNode right = lowestCommonAncestor(root.right,p,q);
if(left == null && right == null) return null;
if(left != null && right == null) return left;
if(left == null && right != null) return right;
return root;
}
}22.二叉搜索树的最近公共祖先：搜索树有序（相当于自带方向） 从上到下遍历，cur节点是数值在[p, q]区间中则说明该节点cur就是最近公共祖先
// class Solution {
// public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// if(root == null) return null;
// int minval = Math.min(p.val,q.val);
// int maxval = Math.max(p.val,q.val);
// if(root.val >= minval && root.val <= maxval){
// return root;
// }
// if(root.val > maxval){
// return lowestCommonAncestor(root.left,p,q);
// }
// if(root.val < minval){
// return lowestCommonAncestor(root.right,p,q);
// }
// return root;
// }
// }
//简化版
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null) return null;
if(root.val < p.val && root.val < q.val) return lowestCommonAncestor(root.right,p,q);
if(root.val > p.val && root.val > q.val) return lowestCommonAncestor(root.left,p,q);
return root;
}
}边栏推荐
- 自媒体创作怎样提高原创度，打造爆款作品？
- 图论之Prim，最小生成树该怎么解?
- Openlayers Quick Start Tutorial
- ThinkPHP 5.1反序列化分析和poc
- 汉源高科千兆12光12电管理型工业以太网交换机 12千兆光12千兆电口宽温环网交换机
- 【C语言】函数哪些事儿，你真的get到了吗？(2)
- Ribbon负载均衡的深度分析和使用
- How to use the database like tap water?｜Tencent Cloud Database TDSQL-C
- 动态组件-component
- "Second Uncle" is popular, do you know the basic elements of "exploding" short videos from the media?
猜你喜欢
随机推荐
图论之Floyd,多源图最短路如何暴力美学？
selenium chrome driver运行时的cannot determine loading status from target frame detached问题
photo-sphere-viewer Chinese documentation
【C语言】夏日一题 —— 求最大公约数和最小公倍数
ThinkPHP 5.1反序列化分析和poc
In-depth analysis and use of Ribbon load balancing
【C语言】虐打循环结构练习题
图文短视频自媒体怎么创作？如何让点击量达到10W？
企业用直播平台能实现什么
FreeRTOS creation tasks - dynamic creation, static creation
this的绑定指向详细解答
SQL Server 2019 installation error 0 x80004005 service there is no timely response to the start or control request a detailed solution
分享一个Chrome控制台数据获取的例子
【C语言】手把手带你写游戏 —— 猜数字
The uniapp/applet onload method executes the interpretation every time the page is opened
RESTful style (detailed introduction + case implementation)
图论之Kruskal,最小生成树如何优雅解题？
FreeRTOS--优先级实验
String concatenation in SQL
SQL Server database generation and execution of SQL scripts