二叉树的一些基本操作
目录
前言：
前序遍历
代码实现
中序遍历
代码实现
后续遍历
代码实现
二叉树节点的个数
代码实现
获取叶子节点的个数
代码实现
获取第K行节点个数
代码实现
二叉树的最大高度
代码实现
二叉树中查找某个数据
代码实现
层序遍历二叉树
代码实现
根据前序遍历字符串构建一颗二叉树
代码实现
小结：
前言：
😆二叉树是一颗结构非常特殊的树，每个节点的度都是小于等于2且大于等于0。树是用递归来定义的，而递归的核心思想是子问题思路，那么大多数处理树相关问题，也需这样去思考。
前序遍历
顺序：根-->左子树-->右子树
🪖在理解子问题思路时，这张图就相当重要。当遍历完根的时候，递归左子树。左子树又是一颗全新的二叉树（左边黑色框框）。到B这个节点的时候，先访问根节点，然后又去递归左子树。到D这个节点，D作为根，又是一颗全新的二叉树（左边绿色框框），然后去递归D的左右子树，都为空，则返回。这时候说明B的左子树遍历完成（回退），去递归B的右子树。E又作为一颗全新的二叉树，分别递归它的左右子树。当A的左右子树全部递归完成后，这时候前序遍历算完成了。
代码实现
public void preOrder(TreeNode root) {
if(root == null) {
return;
}
System.out.print(root.val + " ");
preOrder(root.left);
preOrder(root.right);
}注意：写递归代码时把握好递推公式（如何去递归），然后是递归的结束条件。
中序遍历
顺序：左子树-->根-->右子树
🤨思路和前序遍历思路是一致的，只是每个节点访问的时机不同。这里我画一张递归展开图，帮助去理解。
代码实现
public void inOrder(TreeNode root) {
if(root == null) {
return;
}
inOrder(root.left);
System.out.print(root.val + " ");
inOrder(root.right);
}后续遍历
顺序：左子树-->右子树-->根
😆思路也和前面一致，先去递归左子树，然后递归右子树，最后访问根节点。
代码实现
public void postOrder(TreeNode root) {
if(root == null) {
return;
}
postOrder(root.left);
postOrder(root.right);
System.out.print(root.val + " ");
}二叉树节点的个数
😯还是子问题思路，每棵树节点个数都是左子树节点个数 + 右子树节点个数 + 1（根节点）。然后考虑递归结束条件：当初树为空时，返回即可。
注意：在脑海中要能想到这样的递归过程。累加就是在递归回退的过程中。
代码实现
public int size(TreeNode root) {
if(root == null) {
return 0;
}
return size(root.left) + size(root.right) + 1;
}获取叶子节点的个数
🧢同样是子问题思路，左子树叶子节点个数 + 右子树叶子节点个数。考虑递归结束条件：当树为空时，这时候直接返回0。当递归到叶子节点的时候，返回1。（累加过程也是在递归回退的时候）
代码实现
public int getLeafNodeCount(TreeNode root) {
if(root == null) {
return 0;
}
if(root.right == null && root.left == null) {
return 1;
}
return getLeafNodeCount(root.left) + getLeafNodeCount(root.right);
}获取第K行节点个数
🎄假设获取第3行节点个数，用K去控制递归的层数。相对于第一行是求第三行节点个数，相对于第二行是求第二行节点个数，相对于第三行是求第一行节点个数。则只需要求出当K为1时，节点个数即可。
代码实现
public int getKLevelNodeCount(TreeNode root, int k) {
if(root == null || k <= 0) {
return 0;
}
if(k == 1) {
return 1;
}
return getKLevelNodeCount(root.left, k - 1) + getKLevelNodeCount(root.right, k - 1);
}二叉树的最大高度
🎉递归计算出左右子树的最大高度，然后比较，输出最大的值 + 1（根节点）。高度的累加也是在递归回退的过程。我们在脑海中要能想清楚这样的递归过程。
代码实现
public int getHight(TreeNode root) {
if(root == null) {
return 0;
}
int tmp1 = getHight(root.left);
int tmp2 = getHight(root.right);
return tmp1 > tmp2 ? tmp1 + 1: tmp2 + 1;
}二叉树中查找某个数据
😉可以采取前序遍历法去遍历整棵树，只不过在递归左右子树时，去判断，如果符合条件就返回，不在去递归。
代码实现
public TreeNode find(TreeNode root, char val) {
if(root == null) {
return null;
}
if(root.val == val) {
return root;
}
TreeNode tmp1 = find(root.left, val);
if(tmp1 != null) {
return tmp1;
}
TreeNode tmp2 = find(root.right, val);
if(tmp2 != null) {
return tmp2;
}
return null;
}层序遍历二叉树
层序遍历规则：从上到下，从左到右。
🎈这里采取队列结构特点，队列是怎么入队就怎么出队，入队和出队的顺序是一致的。那么我们只需要保证二叉树从上到下，从左到右去入这个队列，出队时就能保证也是这个顺序。
🎈可以采取用cur去遍历整棵树，树根肯定是层序遍历的第一个数据，直接入树根到队列，判断队列为不为空，不为空则出队列给cur，然后打印数据。接下来分别入根的左右子树，然后再去判断队列，不为空则出左子树给cur，打印数据，再入这棵树的左右子树，出根的右树给cur，打印数据，再入这棵树的左右子树，依次循环直到队列为空。
代码实现
public void levelOrder(TreeNode root) {
if(root == null) {
return;
}
Queue<TreeNode> queue = new LinkedList<>();
TreeNode cur = root;
queue.offer(cur);
while(!queue.isEmpty()) {
cur = queue.poll();
System.out.print(cur.val + " ");
if(cur.left != null) {
queue.offer(cur.left);
}
if(cur.right != null) {
queue.offer(cur.right);
}
}
}根据前序遍历字符串构建一颗二叉树
😊"abc##de#g##f###"，这是一个前序遍历的字符串，#代表空树。我们也根据前序遍历去构建这颗二叉树，如果不为空树就去new节点，然后递归去构建这个节点的左右子树，是#就继续向后遍历字符串。
🤨需要注意的是我们需要一个变量去遍历字符串，而我们采用的是递归的方式，如果是局部变量，那么每次递归进来的时候，该变量都会被重置。所以考虑将该变量定义为成员属性，可以起到累加的效果。
代码实现
private static int i = 0;
public static TreeNode createTree(String str) {
//先构造根节点，然后递归构造左右子树
char tmp = str.charAt(i);
TreeNode newNode = null;
if(tmp != '#') {
i++;
newNode = new TreeNode(tmp);
newNode.left = createTree(str);
newNode.right = createTree(str);
}else {
i++;
}
return newNode;
}小结：
🐵对于二叉树的一些操作，最关键的就是递归的核心思想：子问题思路。需要我们大量去思考，去实践。