【Java】/* 二叉树 - 底层实现*/

一、前序遍历 - 递归

/* 1. 前序遍历 - 递归 */
    public void preOrder(TreeNode root) {
        //1. 如果根节点为null
        if (root == null) {
            return;
        }

        //本意：打印树的根，左，右节点

        //2. 打印根节点的值
        System.out.print(root.val + " ");
        //3. 如果root.left也有左，右节点...，
        //   我们直接使用sout打印root.left.val...会造成打印不全。
        //   既然子树也是树，那么我们可以利用方法的递归去处理
        preOrder(root.left);
        preOrder(root.right);
    }

二、中序遍历 - 递归

/* 2. 中序遍历 - 递归 */
    public void inOrder(TreeNode root) {
        //1. 如果根节点为null
        if (root == null) {
            return;
        }

        //本意：打印树的左，根，右节点

        //2. 如果root的左树也是一颗完整的树，
        //   此时直接打印root.left会造成打印不完全的现象
        //   既然如此，我们可以利用递归先打印root.left再打印当前树的根节点
        inOrder(root.left);
        //3. 打印根节点的值
        System.out.print(root.val + " ");
        //4. 打印root右树
        preOrder(root.right);
    }

三、后续遍历 - 递归

/* 3. 后续遍历 - 递归 */
    public void postOrder(TreeNode root) {
        //1. 如果根节点为null
        if (root == null) {
            return;
        }

        //本意：打印树的左，右，根节点

        //2. 如果root的左树也是一颗完整的树，
        //   此时直接打印root.left会造成打印不完全的现象
        //   既然如此，我们可以利用递归先打印root.left再打印当前树的右树和根节点
        postOrder(root.left);
        postOrder(root.right);
        //3. 打印根节点的值
        System.out.print(root.val + " ");
    }

【小结】：

1. 之所以用到递归是由于root的左树，右树也是一颗完整的树，想要打印完整得先采用递归打印root的左树，右树，而不是直接用sout打印root.left，root.right。

2. 通过画图分析可知，当发现一个节点A的left节点为null时，会返回，使得代码回退到节点A的栈帧中，继续执行后面的打印节点A的right节点的代码。

四、其他方法

package bagone;

import javax.management.relation.InvalidRoleInfoException;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: tangyuxiu
 * Date: 2024-08-26
 * Time: 18:43
 */
public class MyBinaryTree {
    /* 使用内部类来表示树的节点 */
    private static class TreeNode {
        char val;
        TreeNode left;
        TreeNode right;

        public TreeNode(char val) {
            this.val = val;
        }
    }

    /* 1. 前序遍历 - 递归 */
    public void preOrder(TreeNode root) {
        //1. 如果根节点为null
        if (root == null) {
            return;
        }

        //本意：打印树的根，左，右节点

        //2. 打印根节点的值
        System.out.print(root.val + " ");
        //3. 如果root.left也有左，右节点...，
        //   我们直接使用sout打印root.left.val...会造成打印不全。
        //   既然子树也是树，那么我们可以利用方法的递归去处理
        preOrder(root.left);
        preOrder(root.right);
    }

    /* 2. 中序遍历 - 递归 */
    public void inOrder(TreeNode root) {
        //1. 如果根节点为null
        if (root == null) {
            return;
        }

        //本意：打印树的左，根，右节点

        //2. 如果root的左树也是一颗完整的树，
        //   此时直接打印root.left会造成打印不完全的现象
        //   既然如此，我们可以利用递归先打印root.left再打印当前树的根节点
        inOrder(root.left);
        //3. 打印根节点的值
        System.out.print(root.val + " ");
        //4. 打印root右树
        preOrder(root.right);
    }

    /* 3. 后续遍历 - 递归 */
    public void postOrder(TreeNode root) {
        //1. 如果根节点为null
        if (root == null) {
            return;
        }

        //本意：打印树的左，右，根节点

        //2. 如果root的左树也是一颗完整的树，
        //   此时直接打印root.left会造成打印不完全的现象
        //   既然如此，我们可以利用递归先打印root.left再打印当前树的右树和根节点
        postOrder(root.left);
        postOrder(root.right);
        //3. 打印根节点的值
        System.out.print(root.val + " ");
    }

    /* 4. 树的节点个数 - 子问题思路 */
    public int size(TreeNode root) {
        //1. 如果根节点为null
        if (root == null) {
            return 0;
        }

        //2. 根节点1 + 左树节点个数 + 右树节点数
        return 1 + size(root.left) + size(root.right);
    }

    /* 4. 树的节点个数 - 遍历思路 */
    public int sizeTreeNode;
    public void sizeTwo(TreeNode root) {
        //1. 如果根节点为null
        if (root == null) {
            return;
        }

        //本质：遍历树的根，左，右如果不为空sizeTreeNode的值就++

        //2. 根节点算一个所以++
        sizeTreeNode++;

        //3. root的左树，右树节点个数
        //   这里不可能直接下成判断不为null后sizeTreeNode的值就++
        //   因为root的左，右节点也是一颗树，下列代码中不接收返回值，
        //   或着说size方法的返回值为什么要定义成void是因为，我们已经定义了成员变量去记录成员个数了
        //   不用多此一举
        size(root.left);
        size(root.right);
    }

    /* 5. 获取叶子节点的个数 - 子问题思路 */
    public int getLeafNodeCount(TreeNode root) {
        //1. 如果根节点为null
        if (root == null) {
            return 0;
        }

        //2. 如果根节点的左右子树都为null
        if (root.left == null && root.right == null) {
            return 1;
        }

        //3. 收集左树，右树的叶子节点个数
        return getLeafNodeCount(root.left) + getLeafNodeCount(root.right);
    }

    /* 5. 获取叶子节点的个数 - 遍历思路 */
    public int sizeLeafNode;
    public void getLeafNodeCountTwo(TreeNode root) {
        //1. 如果根节点为null
        if (root == null) {
            return;
        }

        //2. 如果根节点的左右子树都为null
        if (root.left == null && root.right == null) {
            sizeLeafNode++;
        }

        //3. 收集左树，右树的叶子节点个数
        getLeafNodeCount(root.left);
        getLeafNodeCount(root.right);
    }

    /* 6. 获取第K层节点的个数 */
    public int getKLevelNodeCount(TreeNode root, int k) {
        //条件：所给的k一定是合法的
        //1. 如果根节点为null（递归的过程中也会出现root为null的情况）
        if (root == null) {
            return 0;
        }

        //2. k == 1
        if (k == 1) {
            return 1;
        }

        //3. 求root的左树，右树的第k-1层
        return getKLevelNodeCount(root.left, k - 1) + getKLevelNodeCount(root.right, k - 1);
    }

    /* 7. 获取二叉树的高度 */
    public int getHeight(TreeNode root) {
        //1. 如果根节点为null
        if (root == null) {
            return 0;
        }

        // 核心：一棵树的高度等于，左树右树相比较的高度max + 1

        int hightOne = getHeight(root.left);
        int hightTwo = getHeight(root.right);
        return Math.max(hightOne,hightTwo) + 1;
    }

    /* 8. 检测值为value的元素是否存在 */
    public TreeNode find(TreeNode root, char val) {
        //1. 如果根节点为null
        if (root == null) {
            return root;
        }

        //2. 判断根节点的值是否为val
        if (root.val == val) {
            return root;
        }

        //3. root的左树，右树，是否存在val值
        TreeNode valNode = find(root.left, val);
        if (valNode != null) {
            return valNode;
        }

        valNode = find(root.right, val);
        //4. 不管是否为null，直接返回valNode中的值即可
        return valNode;
    }
}