二叉树算法练习
二叉树算法题练习。
1.为什么使用二叉树？
-
数组存储方式
1）优点：可以通过下标进行访问
2）缺点：检索某个值，或者插入需要整体移动，效率低。 -
链式存储结构
1）一定程度对数据存储的优化
2）缺点，检索的效率低 -
树存储
可以提高数据的存储、读取效率，比如二叉排序，既可以保证速度，也可以保证数据插入、删除、修改速度。 -
树常用的术语
1）节点
2）根节点
3）父节点
4）子节点
5）叶子结点
6）节点的权
7）路径
8）层
9）子树
10)树高
11）森林
二叉树的概念
树有很多中，每个节点最多可以有两个子节点的叫二叉树。二叉树只有作左节点，右节点。
性质：
1）如果二叉树的所有叶子节点都在最后一层，那么节点的总数为2^n-1,称谓满二叉树。
2）如果二叉树的叶子结点都在最后一层或者倒数第二层，最后一层的叶子节点左边连续，倒数第二层的右边连续。称为完全二叉树。
遍历
使用前中后续遍历。
前：
public void trav(TreeNode root){
if (root!=null){
System.out.println(root.val);
trav(root.left);
trav(root.right);
}
}
中：
public void trav(TreeNode root){
if (root!=null){
trav(root.right);
System.out.println(root.val);
trav(root.left);
}
}
后续
public void trav(TreeNode root){
if (root!=null){
trav(root.right);
trav(root.left);
System.out.println(root.val);
}
}
算法题：
给定一个二叉树的根节点 root ，返回它的中序遍历。
输入：root = [1,null,2,3]
输出：[1,3,2]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-inorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解答：
中序遍历：
public void trav(TreeNode root, ArrayList<Integer> list){
if (root!=null){
trav(root.left,list);
list.add(root.val);
trav(root.right,list);
}
}
这个其实就是考察中序遍历。
给你一个整数 n ，请你生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同 二叉搜索树 。可以按 任意顺序 返回答案。
输入：n = 3
输出：[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]
示例 2：
输入：n = 1
输出：[[1]]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/unique-binary-search-trees-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解答：
不同组合的左右树，会遍历出不同的结果，但是到达最后会只存在两个节点，类似于排列组合。
public List<TreeNode> generaTree(int start,int end){
List<TreeNode> list = new ArrayList<>();
if (start > end){
list.add(null);
return list;
}
for (int i = start; i <= end; i++) {
List<TreeNode> leftNodes = generaTree(start,i-1);
List<TreeNode> rightNodes = generaTree(i+1,end);
for (TreeNode leftNode : leftNodes) {
for (TreeNode rightNode : rightNodes) {
TreeNode current = new TreeNode(i);
current.left = leftNode;
current.right = rightNode;
list.add(current);
}
}
}
return list;
}
这个虽然不是后续遍历，但是 也用到了类似于后续遍历的方法。
给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
输入：n = 3
输出：5
示例 2：
输入：n = 1
输出：1
出处：unique-binary-search-trees/
求个数，不要结果，一般先考虑动态规划。
public int numTrees(int n) {
if (n == 0) {
return 1;
}
int dp[] = new int[n+1];
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; ++i) {
for (int j = 1; j <= i; ++j) {
dp[i] += dp[j - 1] * dp[i - j];
}
}
return dp[n];
}
动态规划 ：一般有三件事做,
- 数组 代表什么东西
- 转移方程怎么写（一般确定了可以使用动态规划，如果不能确定转移方程，可以通过几个案例来推断）
- 写代码
动态规划 ，到动态规划在说。
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
示例 1:
输入:
2
/
1 3
输出: true
示例 2:
输入:
5
/
1 4
/
3 6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
根节点的值为 5 ，但是其右子节点值为 4 。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/validate-binary-search-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
这个题我开始的代码是这样的，
private int lastVla = Integer.MAX_VALUE;
private boolean flag = true;
public boolean isValidBST(TreeNode root) {
trav(root);
return flag;
}
public void trav(TreeNode root) {
if (flag==false)return;
if (root != null) {
trav(root.left);
if (lastVla == Integer.MAX_VALUE){
lastVla = root.val;
}else if (lastVla>=root.val){
flag = false;
}else {
lastVla = root.val;
}
trav(root.right);
}
}
但是有个问题就是：
测试 案例有个值就取到了最大值。
中序遍历有个性质就是，输出的数据是一个有序的，所以我们可以将值记录下来，然后进行比较，后面的大于前面的。
public boolean isValidBST(TreeNode root) {
ArrayList<Integer> list = new ArrayList<>();
trav(root,list);
for (int i = 1; i < list.size(); i++) {
if (list.get(i-1)>=list.get(i)){
return false;
}
}
return true;
}
public void trav(TreeNode root, ArrayList<Integer> list) {
if (root != null) {
trav(root.left, list);
list.add(root.val);
trav(root.right, list);
}
}
