二叉树的一些基本操作

目录

前言：

前序遍历

代码实现 

中序遍历

 代码实现

后续遍历

代码实现

二叉树节点的个数

代码实现

获取叶子节点的个数

代码实现

获取第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 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;
    }

小结：

🐵对于二叉树的一些操作，最关键的就是递归的核心思想：子问题思路。需要我们大量去思考，去实践。