算法篇-二叉树

二叉树的遍历

分为前序、中序和后续的遍历，思想就是利用递归。

前序遍历-中左右

代码：

    public void travelTree(TreeNode node, List<Integer> resulst) {
        if (node == null){
            return;
        }
		
		// 中
        resulst.add(node.val);
        // 左
        travelTree(node.left, resulst);
        // 右
        travelTree(node.right, resulst);
    }
1
2
3
4
5
6
7
8
9
10
11
12

中序遍历-左中右

代码：

public void travelTree(TreeNode node, List<Integer> resulst) {
        if (node == null) {
            return;
        }
		// 左
        travelTree(node.left, resulst);
        // 中
        resulst.add(node.val);
        // 右
        travelTree(node.right, resulst);
    }
1
2
3
4
5
6
7
8
9
10
11

后序遍历-左右中

代码：

public void travelTree(TreeNode node, List<Integer> resulst) {
        if (node == null) {
            return;
        }
		// 左
        travelTree(node.left, resulst);
        // 右
        travelTree(node.right, resulst);
        // 中
        resulst.add(node.val);
    }
1
2
3
4
5
6
7
8
9
10
11

层序遍历

就是一层一层往下遍历就行了。

题目：求一个二叉查找树(BST)的第K大的数

什么是二叉查找树（BST）：BST树的特性如下：

解题思路：根据树的特性，对树进行中序遍历，最后取第k大的数即可。