微信网站开发用什么语言,无锡市网站,wordpress tags页面,wordpress 主题大全文章目录 一、二叉树前中后遍历二、获取节点个数三.获取叶子节点个数四.获取第k层节点个数五.求二叉树的高度#xff0c;时间复杂度O#xff08;N#xff09;六.检测值为value的元素是否存在七. 检查两颗树是否相同八.判断一棵二叉树是不是平衡二叉树九.一个二叉树的根节点 … 文章目录 一、二叉树前中后遍历二、获取节点个数三.获取叶子节点个数四.获取第k层节点个数五.求二叉树的高度时间复杂度ON六.检测值为value的元素是否存在七. 检查两颗树是否相同八.判断一棵二叉树是不是平衡二叉树九.一个二叉树的根节点 root 检查它是否轴对称十. 判断subRoot是不是root的子树十一.翻转二叉树总结 一、二叉树前中后遍历
public class BinaryTree {static class TreeNode{public char val;public TreeNode left;public TreeNode right;public TreeNode(char val) {this.val val;}}public TreeNode creatTree(){TreeNode A new TreeNode(A);TreeNode B new TreeNode(B);TreeNode C new TreeNode(C);TreeNode D new TreeNode(D);TreeNode E new TreeNode(E);TreeNode F new TreeNode(F);TreeNode G new TreeNode(G);TreeNode H new TreeNode(H);A.left B;A.right C;B.left D;B.right E;C.left F;C.right G;E.right H;return A;}//前序遍历void preOrder(TreeNode root){//根左右if(root null){return;}System.out.print(root.val );preOrder(root.left);preOrder(root.right);}//中序遍历void inOrder(TreeNode root){//左根右if(root null){return;}inOrder(root.left);System.out.print(root.val );inOrder(root.right);}//后序遍历void postOrder(TreeNode root){//左右根if(root null){return;}postOrder(root.left);postOrder(root.right);System.out.print(root.val );}public static void main(String[] args) {BinaryTree binaryTree new BinaryTree();BinaryTree.TreeNode root binaryTree.creatTree();binaryTree.preOrder(root);System.out.println();binaryTree.inOrder(root);System.out.println();binaryTree.postOrder(root);}
}二、获取节点个数 public int nodeSize;int size(TreeNode root){if (root null){return 0;}nodeSize;size(root.left);size(root.right);return nodeSize;}//子问题思路解决整棵树的节点左子树的节点右子数的节点1int size2(TreeNode root){if (root null){return 0;}return size2(root.left)size2(root.right)1;}三.获取叶子节点个数
public int leafSize;int getLeafNodeCount(TreeNode root){if (root null){return 0;}if (root.left null root.right null){leafSize;}getLeafNodeCount(root.left);getLeafNodeCount(root.right);return leafSize;}四.获取第k层节点个数 public int leveSize;int getleveNodeCount(TreeNode root,int k){if(root null){return 0;}if (k 1) {return 1;}return getleveNodeCount(root.left,k-1) getleveNodeCount(root.right,k-1);}五.求二叉树的高度时间复杂度ON
int getHeight(TreeNode root){if (root null){return 0;}int leftHeight getHeight(root.left);int rightHeight getHeight(root.right);return leftHeight rightHeight?leftHeight1:rightHeight1;}六.检测值为value的元素是否存在
TreeNode find(TreeNode root,int 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;}七. 检查两颗树是否相同 public boolean isSameTree(TreeNode p, TreeNode q) { if( (p null q !null) || (p ! null q null) ){return false;}if(p null q null){return true;}if(p.val !q.val){return false;}return isSameTree(p.left,q.left) isSameTree(p.right,q.right);}八.判断一棵二叉树是不是平衡二叉树
时间复杂度ON public boolean isBalanced(TreeNode root) {if(root null){return true;}return getHeight(root)0;}int getHeight(TreeNode root) {if (root null){return 0;}int leftHeight getHeight(root.left);if(leftHeight 0){return -1;}int rightHeight getHeight(root.right);if(leftHeight 0 rightHeight 0 Math.abs(leftHeight - rightHeight) 1){return Math.max(leftHeight,rightHeight)1;}else{return -1;}}九.一个二叉树的根节点 root 检查它是否轴对称
public boolean isSymmetric(TreeNode root) {if(root null) return true;return isSymmetricChild(root.left,root.right);}private boolean isSymmetricChild(TreeNode leftTree,TreeNode rightTree){if((leftTree null rightTree ! null) ||(leftTree ! null rightTree null)){return false;}if(leftTree null rightTree null){return true;}if(leftTree.val ! rightTree.val){return false;}return isSymmetricChild(leftTree.left,rightTree.right) isSymmetricChild(leftTree.right,rightTree.left);}十. 判断subRoot是不是root的子树
//时间复杂度O(m*n)public boolean isSubtree(TreeNode root,TreeNode subTree) {if(root null || subTree null) {return false;}//判断根节点是否相同if (isSameTree(root,subTree)){return true;}//判断左子树是否相同if(isSubtree(root.left, subTree)) {return true;}//判断右子树是否相同if(isSubtree(root.right, subTree)) {return true;}return false;}public boolean isSameTree(TreeNode p, TreeNode q) {if( (p null q !null) || (p ! null q null) ){return false;}if(p null q null){return true;}if(p.val !q.val){return false;}return isSameTree(p.left,q.left) isSameTree(p.right,q.right);}十一.翻转二叉树 public TreeNode invertTree(TreeNode root){if(root null){return null;}if(root.left null root.right null){return root;}//交换左右节点TreeNode tmp root.left;root.left root.right;root.right tmp;//交换左树invertTree(root.left);//交换右树invertTree(root.right);return root;}总结
今天复习二叉树练习。 时隔一个月继续更新文章学校的考试周太可怕了. 怕挂科所以全身心投入复习平时都学编程了学校的课靠最后几周学完全部也是挺厉害的哈哈。
