网站子页面设计,雅安建设网站,网站运营需要哪些知识,中标查询二叉树Oj题 获取二叉树的节点数获取二叉树的终端节点个数获取k层节点的个数获取二叉树的高度检测为value的元素是否存在判断两颗树是否相同判断是否是另一棵的子树反转二叉树判断一颗二叉树是否是平衡二叉树时间复杂度O(n*n)复杂度O(N) 二叉树的遍历判断是否是对称的二叉树二叉… 二叉树Oj题 获取二叉树的节点数获取二叉树的终端节点个数获取k层节点的个数获取二叉树的高度检测为value的元素是否存在判断两颗树是否相同判断是否是另一棵的子树反转二叉树判断一颗二叉树是否是平衡二叉树时间复杂度O(n*n)复杂度O(N) 二叉树的遍历判断是否是对称的二叉树二叉树的层序遍历 获取二叉树的节点数
首先从左树开始递到最下一层当最后一层H没有节点时归回1以此类推最终返回的节点就是我们树的节点树。
public int getNodeCount(TreeNode root){if(rootnull)return 0;return getNodeCount(root.left)getNodeCount(root.right)1;}获取二叉树的终端节点个数
首先清楚二叉树的终端结点是什么 终端结点说明它的度为0没有子树所以左树和右树的值为null而我们就只需要判断一下如果左树和右树值为null则就是一个叶子结点1. public int getLeafCount(TreeNode root){if(rootnull)return 0;if(root.leftnullroot.rightnull){return 1;}return getLeafCount(root.left)getLeafCount(root.right);}获取k层节点的个数
第一层为我们的根节点它的个数一定是1而根的左树和右树则为2以此类推 首先我们的第一个条件是k为1时一定会有一个节点数 这里当我们递出去时我们就会减少一层当k等于1时这里我们就在k层找到一个节点然后回归到父节点然后继续子树找下一个节点知道将k层的节点数遍历完。 public int getLevelCount(TreeNode root,int k){if(rootnull)return 0;if(k1)return 1;return getLevelCount(root.left,k-1)getLevelCount(root.right,k-1);}获取二叉树的高度
这里直接求左子树的最大高度和右子树的最大高度然后进行比较然后返回最大的高度值就可以 public int getBinaryTreeHeight(TreeNode root){if(rootnull)return 0;int maxtLeftHeightgetBinaryTreeHeight(root.left);int maxRightHeightgetBinaryTreeHeight(root.right);return maxLeftHeightmaxRightHeight?maxLeftHeight1:maxRightHeight1;}检测为value的元素是否存在
首先root根和递归的条件不能为空 然后判断root的值是否为value值并返回这个值 用一个ret来接收其返回值然后判断ret不为空则回来的值将root的value值带回 ret如果为空说明root根或者递归的条件就是空的没有要找的元素
public TreeNode find(TreeNode root,String val){if(rootnull)return null;if(root.val.equals(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 tree1,TreeNode tree2){//两棵树如果同时走一个有节点一个没有节点一定不相同if(tree1nulltree2!null||tree1!nulltree2null)return false;//两棵树都为null说明都没有可以走的节点if(tree1nulltree2null)return true;//判断结构//判断节点值是否相同不同为falseif(!tree1.val.equals(tree2.val)return false;return isSameTree(tree1.left,tree2.left)isSameTree(tree1.right,tree2.right);}判断是否是另一棵的子树
判断是否是tree中的一颗子树subtree一定是t在ree中头节点左子树中或者是右子树中如果不在这里直接返回false 这里由tree的左子树和右子树递归找到subtree的根节点找到后将tree中的subtree子树与subtree同时遍历来确认是否为一个相同的树。 public boolean isSubtree(TreeNode root, TreeNode subRoot) {//是相同的树节点返回trueif(isSameTree(root,subRoot))return true;//递归如果出现root为null时因为没有语句拦截root会继续往下走导致空指针异常//subRoot为null直接返回false主树不在进行下面的递归if(rootnull||subRootnull)return false;if(isSubtree(root.left,subRoot))return true;if(isSubtree(root.right,subRoot))return true;return false;}反转二叉树
将二叉树的每个节点的左子树和右子树互换 public TreeNode invertTree(TreeNode root) {if(rootnull)return null;TreeNode tmproot.left;root.leftroot.right;root.righttmp;invertTree(root.left);invertTree(root.right);return root;}判断一颗二叉树是否是平衡二叉树
时间复杂度O(n*n)
该题判断二叉树是否是平衡二叉树的条件是左子树与右子树的绝对值一定小于或者等于1如果高度大于1则非平衡二叉树。 如果根节点只有一个节点或者他的左右子树差的绝对值为0则为平衡二叉树 只判断了根的节点的话它的左右子树的差确实为1但是左子树中b的左子树和右子树的差值为2这也不是一个平衡的二叉树。 public boolean isBalanced(TreeNode root) {if(rootnull)return true;//root为null直接返回为空int leftHeight maxDepth(root.left);//求左树的高度int rightHeight maxDepth(root.right);//求右树的高度return Math.abs(leftHeight-rightHeight)1//判断isBalanced(root.left)isBalanced(root.right);}public int maxDepth(TreeNode root){//求二叉树的最大深度if(rootnull)return 0;int leftHeightmaxDepth(root.left);int rightHeightmaxDepth(root.right);return leftHeightrightHeight?leftHeight1:rightHeight1;}复杂度O(N) 这里如果我们在找左右子树高度的差值时如果发现了它差值大于1的情况我们直接返回-1当最后回归到根节点左右子树时差值也大于1
class Solution {public boolean isBalanced(TreeNode root) {if(rootnull)return true;int ret maxDepth(root);//接收ret为-1则左右子树差值一定大于1if(ret-1){return false;}return true;}public int maxDepth(TreeNode root){//求二叉树的最大深度if(rootnull)return 0;int leftHeightmaxDepth(root.left);int rightHeightmaxDepth(root.right);//走到这里最靠下的边上的左右子树求得高度if(leftHeight0rightHeight0Math.abs(leftHeight-rightHeight)1){//说明左右子树的绝对值为1并且大于等于0//返回左右子树中最大的一个高度1return Math.max(leftHeight,rightHeight)1;}else{return -1;}}
}二叉树的遍历 首先创建一个类来实现构造二叉树的前提 因为题目条件给定的是输入一串字符串然后先序遍历这个字符串来建立起二叉树然后通过中序遍历在进行打印
class TreeNode {public char val;public TreeNode left;public TreeNode right;public TreeNode(char val) {this.val val;}
}
public class Main {public static int i 0;public static void main(String[] args) {Scanner in new Scanner(System.in);while (in.hasNextLine()) {String strin.nextLine();TreeNode rootcreateTree(str);inOrder(root);}}public static TreeNode createTree(String str) {TreeNode rootnull;//遍历字符串str来获取字符来给到root因为不确定root是不是空节点。if (str.charAt(i) ! #) {root new TreeNode(str.charAt(i));i;//通过i来递归左右树root.leftcreateTree(str);root.rightcreateTree(str);} else {//跳过#i;}return root;}//中序遍历public static void inOrder(TreeNode root) {if (root null)return ;inOrder(root.left);System.out.print(root.val );inOrder(root.right);}判断是否是对称的二叉树
二叉树反转过来的镜像就是对称的二叉树 这里直接从根节点的左树和右树下手 满足条件1:二叉树的结构相同 满足条件2:二叉树的对称值相同 左子树中的左树对应右子树的右树 右子树的左树对应左子树的右树 public boolean isSymmetric(TreeNode root) {if(rootnull)return true;//判断左右节点是否对称return isSymmetricChild(root.left,root.right);}public boolean isSymmetricChild(TreeNode t1,TreeNode t2){//这里t1和t2的结构不相同if(t1nullt2!null||t1!nullt2null)return false;//两者都为空说明结构相同走向空节点if(t1nullt2null)return true;//到这里结构相同检查对称值if(t1.val!t2.val)return false;//满足左右子树的对称条件 return isSymmetricChild(t1.left,t2.right)isSymmetricChild(t1.right,t2.left);}二叉树的层序遍历
二叉树层序遍历是地1层开始从左到右从上到下开始遍历。 如果用二维数组来进行层序遍历怎么做呢 这里需要用到队列因为第一层的根节点永远是1我们将它放入到队列中来遍历这个队列
如果a释放完且a树的值给到了一维数组后会得到b和c两个子树并放到队列中这时候需要一个计数器来计算当前的层数当层数为0时我们将一维数组所有的值放到二维数组中就好了
public ListListInteger levelOrder(TreeNode root) {ListListInteger linenew ArrayListListInteger();if(rootnull)return line;QueueTreeNode queuenew LinkedList();queue.offer(root);while(!queue.isEmpty()){int sizequeue.size();ListInteger colnew ArrayListInteger();while(size!0){TreeNode cur queue.poll();col.add(cur.val);size--;if(cur.left!null) queue.offer(cur.left);if(cur.right!null) queue.offer(cur.right);}line.add(col);}return line;}
