Leetcode 树专题_leetcode上b+树

写一篇树专题。
树，是一种基本的数据结构，它可以用数组和链表两种方法实现。
一开始学的是二叉树，而二叉树里面有分有很多类型，二叉查找树，AVL树，红黑树…等等（真是怕了红黑树，有太多种情况，虐人…
java中的TreeMap的底层就是红黑树，而mysql数据库的索引就是用b+树…（我还没有学数据库，瑟瑟发抖
首先学二叉树的时候会学到遍历方式：前序中序后序遍历，以及层序遍历。
大家可以想象，层序遍历是不是像广度优先搜索，而中序更像是深度优先搜索。

值得一提的是中序遍历的结果一定是升序的。
因为二叉树，它的性质是左儿子小于父节点，而右儿子大于父节点，根据中序遍历，那么结果就一定是升序。
这里简略提一下删除和插入的操作。操作简单，递归找到底层可以放的位置，然后插到最底层。删除的话，分三种情况，为叶子节点，有一个子节点，有两个子节点。其中一二种情况较为简单。也可以合并起来写。
第三种情况需要先找到需要删除的节点，然后从它左边子树里找到叶节点的最大值或从右边子树里找到叶节点的最小值，用这个节点去替代要删除的节点，最后递归的删除这个找到的节点。
我们还是以算法为主，直接来a力扣的题目吧。

94. 二叉树的中序遍历
给定一个二叉树，返回它的中序 遍历。
示例:
输入: [1,null,2,3]
1

2
/
3
输出: [1,3,2]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？

94题。中等难度。实话说它达不到这个难度。
中序遍历应该大家都会

if(root != null) {
inorder(root.left);
printf("%d",root->val);
inorder(root.right);
}
四行代码完事，这题一样可以这样写，而且效率绝对不低。
甚至我测试得是最快的。
但是还是可用迭代的算法， 用一个数据结构，栈。
怎么操作，可以先一直将左节点入栈，然后弹出的时候观察每一个节点它有没有右孩子。没有就pop，有的话就访问右孩子。可以视为每一个pop出来的node都是父节点，这是迭代的写法，但是奇怪的是，效率没有递归高。击败了50+，递归好像可以击败90+，有点奇怪。。

下面是ac代码

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        return dfs(root, ans);
    }
    public List<Integer> dfs(TreeNode root, List<Integer> ans) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode node = root;
        while(node != null || stack.size() > 0) {
            if(node != null) {
                stack.push(node);
                node = node.left; 
            }
            else {
                node = stack.pop();
                ans.add(node.val);
                node = node.right;
            }
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

104. 二叉树的最大深度
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例：
给定二叉树 [3,9,20,null,null,15,7]，
3
/
9 20
/
15 7
返回它的最大深度 3 。
简单题没意思。直接递归解决，击败95。

class Solution {
    public int maxDepth(TreeNode root) {
        return get_height(root);
    }
    public int get_height(TreeNode root) {
        if(root == null) return 0;
        return 1 + Math.max(get_height(root.left), get_height(root.right));
    }
}
1
2
3
4
5
6
7
8
9

222. 完全二叉树的节点个数

给出一个完全二叉树，求出该树的节点个数。
说明：
完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。
示例:
输入:
1
/
2 3
/ \ /
4 5 6
输出: 6

222 可以递归来求解，效率还可以七八十+的样子。
递归对树来说可以解决绝大部分问题。
但是有其他更高效的方法，这一题，可以利用它完全二叉树的特性。
时间复杂度在O（logN * logN)
这里可以求左子树和右子树的高度
如果两子树高度一样，那么就不需要递归的求左子树的节点数，直接pow(2, n) n为层数
而后加上递归求得右子树节点数
如果高度不一样，右子树直接pow（2，n) n为右子树得高度，而后加上左子树得节点数
当然，高度是用递归求。
效率在90+。

class Solution {
    public int countNodes(TreeNode root) {
        if(root == null) return 0;
        int left_son_heigth = get_Height(root.left);
        int right_son_height = get_Height(root.right);
        if(left_son_heigth == right_son_height) {
            return (int) Math.pow(2, left_son_heigth) + countNodes(root.right);
        }
        else return (int) Math.pow(2, right_son_height) + countNodes(root.left);
    }
    
    public int get_Height(TreeNode root) {
        if(root == null) return 0;
        return Math.max(get_Height(root.left), get_Height(root.right)) + 1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

783. 二叉搜索树结点最小距离
给定一个二叉搜索树的根结点 root, 返回树中任意两节点的差的最小值。
示例：
输入: root = [4,2,6,1,3,null,null]
输出: 1
解释:
注意，root是树结点对象(TreeNode object)，而不是数组。
给定的树 [4,2,6,1,3,null,null] 可表示为下图:
4
/
2 6
/ \
1 3
最小的差值是 1, 它是节点1和节点2的差值, 也是节点3和节点2的差值。
注意：
二叉树的大小范围在 2 到 100。
二叉树总是有效的，每个节点的值都是整数，且不重复。

可以递归
还有一个更好的思路，就是用中序遍历，因为中序遍历一定是升序的，然后选择中序遍历里面相邻两个之差最小的那个差，就是答案了。击败90+

class Solution {
    public int minDiffInBST(TreeNode root) {
        List<Integer> ans = new ArrayList<Integer>();
        ans = dfs(root, ans);
        return find(ans);
    }
    public List<Integer> dfs(TreeNode root, List<Integer> ans) {
        if(root != null) {
            dfs(root.left, ans);
            ans.add(root.val);
            dfs(root.right, ans);
        }
        return ans;
    }
    public int find(List<Integer> ans) {
        int n = ans.size();
        int res = ans.get(1) - ans.get(0);
        for(int i = 2; i < n; i ++) {
            res = Math.min(res, (ans.get(i) - ans.get(i - 1)));
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

先更这么多了，最近期末考比较忙
ps. 高数，离散是真的烦！我情愿去学数据结构！！