【Java数据结构 -- 二叉树的基本操作】

二叉树的基本操作

• 1.获取树中节点的个数
• • 1.1 计数器递归的思路
  • 1.2 子问题思路：
  • 2. 获取叶子个数
  • 3. 获取第k层节点的个数
  • 4.获取二叉树的高度
  • 5.���测值为value的元素是否存在

    1.获取树中节点的个数

    思路：整棵树的节点个数 = 左子树的节点个数＋右子树的节点个数+根本身一个。

    （）

    1.1 计数器递归的思路

    定义一个计数器nodesize，先++然后遍历二叉树左子树和右子树。

    public int nodesize;    int size(TreeNode root) {        if(root == null) {            return 0;        }        nodesize++;        size(root.left);        size(root.right);        return nodesize;    }

    1.2 子问题思路：

    整棵树的节点个数 =左子树的节点个数＋右子树的节点个数+根本身一个。

    （）

    int size2(TreeNode root) {        if (root == null) {            return 0;        }        return size2(root.left) + size2(root.right) + 1;    }

    2. 获取叶子个数

    思路：整棵树的叶子 = 左子树的叶子+右子树的叶子。

        int getLeafNodeCount(TreeNode root) {        if (root == null) {            return 0;        }        if(root.left ==null && root.right == null) {            return 1;        }        return getLeafNodeCount(root.left) + getLeafNodeCount(root.right);    }

    3. 获取第k层节点的个数

    思路：整棵树的第k层多少个节点 = 左子树的第k-1个节点 + 右子树的第k-1层节点；

    如 k = 3 A 这颗树的第三层 = A左树（B）的第二层 + A右树（C）的第二层；

    第一层只有一个节点 B左树的第一层+B右树的第一层 C左树的第一层+右第一层。

        int getKLevelNodeCount(TreeNode root,int k) {        if (root == null) {            return 0;        }        if(k == 1) {           return 1;        }        return getKLevelNodeCount(root.left,k-1) +                getKLevelNodeCount(root.right,k-1);    }

    4.获取二叉树的高度

    思路：整棵树的高度 = 左子树的高度 和右子树的高度的最大值 + 1。

        int getHeight(TreeNode root){        if(root == null) {            return 0;        }        int leftHeight = getHeight(root.left);        int rightHeight = getHeight(root.right);        return leftHeight > rightHeight ? leftHeight + 1:rightHeight + 1;    }

    5.检测值为value的元素是否存在

    思路：按照根 - 左 - 右的前序遍历进行遍历，1.是否为空树；2.根的值是不是；3.左子树；4.右子树；

        TreeNode find(TreeNode root,char val) {        if(root == null){            return null;        }        if(root.val == val) {            return root;        }        TreeNode ret1 = find(root.left,val);        if (ret1 != null) {            return ret1;        }        TreeNode ret2 = find(root.right,val);        if (ret2 != null) {            return ret2;        }        return null;    }