二叉树的类由节点值左子树和右子树组成二叉树的基本方法-四种遍历1.先序遍历 - 根左右 - ABDEHCFG 先序遍历的第一个节点一定是根结点没有父节点的节点2.中序遍历 - 左根右 - DBEHAFCG 中序遍历根节点左边全是左子树中序遍历的结果根节点的右边一定是右子树中序遍历的结果3.后序遍历 - 左右根 - DHEBFGCA 后序遍历的最后一个节点一定是根节点4.层序遍历 -二叉树遍历的还原后序先序 不能还原1.后序中序1先找出后序遍历的最后一个节点该节点是根节点A2再把根节点对应到中序遍历结果中 根节点左边的就是左子树中序遍历的结果DBEH根节点右边的就是右子树中序遍历的结果FCG3把左子树DBEH对应到后序遍历中去左子树的后序遍历就是DHEB,中序右子树FCG对应的后序右子树遍历就是FGC再依次类推B就是左子树的根节点C就是右子树的根节点2.先序中序1先找出先序遍历的最前面的一个节点就收根节点A,2) 再把根节点A对应的中序遍历的结果中根节点A左边就是左子树中序遍历的结果根节点右边就是右子树中序遍历的结果3再把中序遍历的左右子树在先序遍历结果里对应BDEH就是左子树先序遍历的CFG就是右子树先序遍历的在以此类推B就是左子树的根节点C就是右子树的根节点总结后序/先序 中序 可以还原出原始的二叉树1根据后序遍历/先序结果找到根节点2根据根节点去中序中查看区分出谁是左子树谁是右子树3) 根据中序知道了左右子树之后再去后序中找对应的子树后序结果方法说明size() - 获取树中结点的个数 - 通过递归来完成递归的初始条件是 rootnull 时 return 0 递归公式是1 size(root.left) size(root.right) 树的节点个数等于1左子树的节点个数右子树的节点个数getLeafCount(TreeNode root) - 获取叶子节点的个数 - 递归来完成 - 初始条件是空树情况下rootnull叶子节点的个数显然为0当root的左右子树都为空时该节点root就是叶子节点 递推公式时 getLeafCount(root.left) getLeafCount(root.right)一棵树的叶子节点就是左子树和右子树的叶子节点相加getKLevelCount(TreeNode root , int k) - 获取第k层的叶子节点个数- 初始条件是ifrootnull || kkreturn 0 ifk 1 return 1 - 递推公式是 一棵树的第k层叶子节点个数左子树第k-1层右子树的第k-1层的叶子节点个数getHeight(TreeNode root) - 获取书的最大高度 - 初始条件root null return 0 root.left null root.right null return1递推公式1Math.max(getHeight(root.left) , getHeight(root.right)find(TreeNode root , int val) - 查找节点 - 也是通过递归来实现的先判定树为空的情况返回null再判定该树的节点值是否等于val 等于就直接返回未找到再递归左子树左子树没有再找右子树通过递归的方式实现遍历层序遍历广度优先搜索 没有递归通过队列来实现获取树种结点的个数获取树中叶子节点的个数获取第k层叶子节点的个数获取数的最大高度查找节点判断一棵树是不是二叉树