前言
之前的博客中,笔者初步介绍了一下二叉树的性质,如何构建二叉树和二叉树的常见方法.
入门数据结构JAVA DS——二叉树的介绍 (构建,性质,基本操作等) (1)-CSDN博客
这篇博客围绕着二叉树的常见方法,介绍一下常见的OJ题目,帮助读者们加深对于二叉树的理解.
虽然本文介绍的是常见的OJ题,但其实还是介绍二叉树常见的构造,存储,遍历.只不过是把这些方法应用于实际的题目当中.
第一题 —— 对称二叉树
101. 对称二叉树 - 力扣（LeetCode）
这道题的本质也就是遍历二叉树吧
1.首先考虑树是不是空的
空的,OK,返回true.
2.考虑root结点的左右子节点想不想同,OK,相同,那就继续看看
左子树的左子树和右子树的右子树
左子树的右子树和右子树的左子树
是不是相同的
本质上就是通过遍历这棵树找到不同的地方,如果找不到,那就是true,找到了,就是false
笔者的答案如下
class Solution {public int pd = 0; // 标记是否发现不对称public boolean ans = true; // 默认树是对称的public boolean isSymmetric(TreeNode root) {if (root == null) {return true; }dfs(root.left, root.right); return ans; } private void dfs(TreeNode left, TreeNode right) {if (pd == 1) {return; // 如果已经发现不对称，直接返回}if (left == null && right == null) {return; }if (left == null || right == null || left.val != right.val) {pd = 1; ans = false;return;}dfs(left.left, right.right);dfs(left.right, right.left);}
}第二题 —— 0黄金树
0黄金树 - 蓝桥云课 (lanqiao.cn)
这道题的本质依旧还是遍历二叉树,根据题意来算权重,只不过是我们需要自己创建数组存储二叉树而已.
先去通过题意去找到那些结点的黄金指数是0,然后再把他们的权重加起来即可.
#include <bits/stdc++.h>
using namespace std;struct tree {int l;int r;
};
const int N = 1e5 + 5;
tree a[N];
int w[N], n;
int sum = 0;void dfs(int deep, int key) {if (key == 0) {sum += w[deep];}if (a[deep].l != -1) {dfs(a[deep].l, key + 1);}if (a[deep].r != -1) {dfs(a[deep].r, key - 1);}
}
int main() {cin >> n;for (int i = 1; i <= n; i++) {cin >> w[i];}for (int i = 1; i <= n; i++) {cin >> a[i].l >> a[i].r;}dfs(1, 0);cout << sum;return 0;
}
第三题 —— 二叉树的最小深度
111. 二叉树的最小深度 - 力扣（LeetCode）
这道题要我们求最小深度,其实和最大深度呼应了,笔者分享自己的代码,我认为这个代码的可读性和灵活性都很强
class Solution {public int minfor;public int minDepth(TreeNode root) {if (root == null) {return 0;}minfor =8000;DFS(root, 1); // 从根节点，深度为1开始return minfor;}private void DFS(TreeNode root, int depth) {// 如果是叶子节点if (root.left == null && root.right == null) {minfor = Math.min(depth, minfor);return;}// 递归左子树if (root.left != null) {DFS(root.left, depth + 1);}// 递归右子树if (root.right != null) {DFS(root.right, depth + 1);}}
}
求最大深度就用max,最小就用min.
第四题 —— 二叉树遍历
还记得笔者写过,构建二叉树大概有两种方式,一种是手动构建,一种是告诉你遍历顺序.
一般来说,知道前序中序或者后序中序,就可以构建出来一颗二叉树.
二叉树遍历_牛客题霸_牛客网 (nowcoder.com)
而我们的这道题,是告诉你那些结点是空结点了,我们就不需要借助中序遍历去验证那些结点是空结点了,难度有所降低
我们的大致思路如下
1.无论如何,我们都要遍历"顺序字符串",如果下标位置的字符不是'#',那么可以肯定,他就是一个结点,我们就需要把它构建出来.
2.根据前序遍历的顺序 —— 根,左,右来看,当构建完根节点或者子根结点以后,就要去构建左子树和右子树——哪怕他们是空的.
import java.util.Scanner;
class TreeNode
{public char val;public TreeNode left;public TreeNode right;public TreeNode (char val){this.val=val;}
}
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static int i=0;public static void main(String[] args) {Scanner in = new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseString str=in.nextLine();TreeNode root=create(str);inorder(root);i=0;}}public static TreeNode create (String str){TreeNode root=null;if(str.charAt(i)!='#'){root=new TreeNode(str.charAt(i));i++;root.left=create(str);root.right=create(str); }else{i++;}return root;}public static void inorder(TreeNode root){if(root==null){return ;}inorder(root.left);System.out.print(root.val+" ");inorder(root.right);}
}结尾
暂时写到这里,感谢大家的支持!!!!