网站商业模板,厦门网站建设报价,讨论建设网站的心得,中国建设银行官网官网二叉树的基本操作
前文对二叉树的递归遍历作了一定的介绍#xff0c;本文中我们继续深入理解递归#xff0c;实现二叉树的基本操作。
1、获取树中结点个数
对于这个问题#xff0c;我们有两种解决的思路。
1、子问题思路
我们通过结点左字树和右字树的结点总数加1来计算…二叉树的基本操作
前文对二叉树的递归遍历作了一定的介绍本文中我们继续深入理解递归实现二叉树的基本操作。
1、获取树中结点个数
对于这个问题我们有两种解决的思路。
1、子问题思路
我们通过结点左字树和右字树的结点总数加1来计算总结点数而左右子树又可以通过这个方法来拆分成求子树的子树的结点总数的问题直到遇到叶子结点递进过程结束开始回归。代码如下
public int size(TreeNode root) {if(root null) {return 0;}return size2(root.left) size2(root.right)1;}2、遍历思路
设置非成员变量nodeSize来计数吗遇到结点就让nodeSize自增。 public static int nodeSize;public void size(TreeNode root) {if(root null) {return;//空树是不需要遍历的}nodeSize;size(root.left);size(root.right);}
2、获取叶子结点个数
相信通过对以上递归的理解可以想出如何获取叶子结点的个数。唯一需要注意的是。叶子结点的判断条件左孩子引用与右孩子引用为空。
public int leafSize;public void getLeafNodeCount(TreeNode root) {if(root null) {return;}if(root.left null root.right null) {leafSize;}getLeafNodeCount(root.left);getLeafNodeCount(root.right);}3、获取第K层节点的个数
这个题目相对于上面的题目参数多了一个k因此在递归时要考虑传入的是k经变化后的值。同时递归的条件也要发生改变应该当k的值为1时停止递进。代码如下 public int getKLevelNodeCount(TreeNode root,int k) {if(root null) {return 0;}if(k 1) {return 1;//就是当前结点个数为1}return getKLevelNodeCount(root.left,k-1)getKLevelNodeCount(root.right,k-1);//向下推移1层k--}4、获取二叉树的高度
对于这个问题我们也是利用这个方法的自调用利用递归实现。值得思考的是二叉树的高度由最下层的结点的高度决定因此我们要取出左右子树中深度中的较大值再加上1根结点得到二叉树的高度。 public int getHeight(TreeNode root) {if(root null) {return 0;}int leftHeight getHeight(root.left);int rightHeight getHeight(root.right);return Math.max(leftHeight,rightHeight) 1;}5、检测值为value的元素是否存在
查找十分简单按照根左右顺序递归查找即可。
public TreeNode find(TreeNode root,int val) {if(root null) return null;if(root.val val) return root;TreeNode leftVal find(root.left,val);if(leftVal ! null) {return leftVal;}TreeNode rightVal find(root.right,val);if(rightVal ! null) {return rightVal;}return null;}
