网站设计任务,新浪sae可以做网站么,商标注册查询官网入口官方,网站菜单栏代码【java数据结构】二叉树OJ题 一、检查两颗树是否相同二、另一颗树的子树三、翻转二叉树四、对称二叉树五、判断一颗二叉树是否是平衡二叉树六、给定一个二叉树, 找到该树中两个指定节点的最近公共祖先七、根据一棵树的前序遍历与中序遍历构造二叉树练习#xff1a;八、二叉树前… 【java数据结构】二叉树OJ题 一、检查两颗树是否相同二、另一颗树的子树三、翻转二叉树四、对称二叉树五、判断一颗二叉树是否是平衡二叉树六、给定一个二叉树, 找到该树中两个指定节点的最近公共祖先七、根据一棵树的前序遍历与中序遍历构造二叉树练习八、二叉树前序非递归遍历实现练习练习 博客最后附有整篇博客的全部代码 一、检查两颗树是否相同
给你两棵二叉树的根节点 p 和 q 编写一个函数来检验这两棵树是否相同。 如果两个树在结构上相同并且节点具有相同的值则认为它们是相同的。 检查两颗树是否相同 解题思路 1.先判断两棵树是否都为空都为空则两棵树是相等的反之一棵树为空另一棵树不为空则两棵树不是相同二叉树。 2.分别进行遍历两棵树的左右节点判断其节点的值是否相等。 public boolean isSameTree(TreeNode p, TreeNode q) {if(pnullqnull)return true;if(pnull||qnull)return false;if(p.val!q.val){return false;}return isSameTree(p.left,q.left)isSameTree(p.right,q.right);}二、另一颗树的子树
给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在返回 true 否则返回 false 。 二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。 另一颗树的子树 解题思路1 1.先判断SubRoot是否为空为空则一定是子树下来判断Root是否为空为空则返回false。 2.自己定义了一个方法isSameTreeNode p,TreeNode q来判断遍历的树的左右节点的值是否相同。 3. return isSubtree(root.left,subRoot)|| 4. isSubtree(root.right,subRoot)||isSame(root,subRoot);这段代码的意思先用isSubtree(TreeNode root, TreeNode subRoot)这个方法遍历Root树的左右节点然后每当遍历到一个节点的时候都将该节点作为Root节点的树和SubRoot树传入到isSameTreeNode p,TreeNode q这个方法中进行判断这两棵树是否相同但凡相同则返回true反之如果遍历完每个节点都和SubRoot树没有完全相同的树则SubRoot就不是Root树的子树。 public boolean isSubtree(TreeNode root, TreeNode subRoot) {if(subRootnull)return true;if(rootnull)return false;return isSubtree(root.left,subRoot)||isSubtree(root.right,subRoot)||isSame(root,subRoot);}public boolean isSame(TreeNode p,TreeNode q){if(pnullqnull)return true;if(pnull||qnull||p.val!q.val)return false;return isSame(p.left,q.left)isSame(p.right,q.right);}三、翻转二叉树
给你一棵二叉树的根节点 root 翻转这棵二叉树并返回其根节点。 翻转二叉树 解题思路 1.先判断Root树是否为空为空则返回null。 2.递归树的每一个节点的左右节点并用定义的TreeNode类型的left和right来进行接收每一个节点的左右节点。 3.最后将left和right互换。 public TreeNode invertTree(TreeNode root) {if(rootnull)return null;TreeNode leftinvertTree(root.left);TreeNode rightinvertTree(root.right);root.leftright;root.rightleft;return root;}四、对称二叉树
给你一个二叉树的根节点 root 检查它是否轴对称。 对称二叉树 解题思路 和判断两棵树是否相同的思路相等不同点是判断的是p的左节点和q的右节点、p的右节点和q的左节点是否相同。 public boolean isSymmetric(TreeNode root) {if(rootnull)return true;TreeNode proot.left;TreeNode qroot.right;return isSame(p,q);}public boolean isSame(TreeNode p,TreeNode q){if(pnullqnull)return true;if(pnull||qnull||p.val!q.val)return false;return isSame(p.left,q.right)isSame(p.right,q.left);}五、判断一颗二叉树是否是平衡二叉树
给定一个二叉树判断它是否是 平衡二叉树。 判断一颗二叉树是否是平衡二叉树
解题思路1 时间复杂度为ON^2 1.先判断树是否为空。 2.遍历每一个节点求每一个节点的左右高度判断该节点的左右高度差是否大于1。 public boolean isBalanced(TreeNode root) {if(rootnull)return true;int leftHightgetHeight(root.left);int rightHightgetHeight(root.right);return Math.abs(leftHight-rightHight)1 isBalanced(root.left) isBalanced(root.right);}int getHeight(TreeNode root) {if (root null) return 0;int leftH getHeight(root.left);int rightH getHeight(root.right);return leftH rightH ? leftH 1 : rightH 1;}解题思路2 时间复杂度ON。 自下而上计算每个节点的高度判断每个节点是否是平衡二叉树如果是返回该节点的高度反之返回-1。 public boolean isBalanced2(TreeNode root) {return getHeight2(root)0;}int getHeight2(TreeNode root) {if (root null) return 0;int leftH getHeight2(root.left);if(leftH0){return -1;}int rightH getHeight2(root.right);if(rightH0Math.abs(leftH - rightH) 1){return Math.max(leftH, rightH) 1;}return -1;}六、给定一个二叉树, 找到该树中两个指定节点的最近公共祖先 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先 解题思路1 1.先判断树是否为空为空则返回null。 2.开始遍历树的每一个节点找到p或q的节点然后返回。 3.如果都找到了则返回Root节点这里的Root节点肯定不是p或q的本身如果没找到q节点则公共祖先就是q节点反之。 此思路当找到一个节点时就不会继续遍历该节点的子节点。 public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(rootnull)return null;if(rootp||rootq)return root;TreeNode lefttreelowestCommonAncestor(root.left,p,q);TreeNode righttreelowestCommonAncestor(root.right,p,q);if(lefttree!nullrighttree!null){return root;}else if(lefttree!null){return lefttree;}else{return righttree;}}解题思路2 1.定义两个栈s1s2。用来保存root节点到目标节点p、q的节点数。 2.判断两个栈的长度pop出栈中元素个数多的栈让两个栈中元素个数相同。 3.peek两个栈栈顶元素判断是否相同相同则就是公共祖先不同则pop出两栈顶元素。 public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {StackTreeNode s1new Stack();StackTreeNode s2new Stack();getPath(root,p,s1);getPath(root,q,s2);if(s1.size()s2.size()){int lens1.size()-s2.size();while(len!0){s1.pop();len--;}}else{int lens2.size()-s1.size();while(len!0){s2.pop();len--;}}while(!s1.isEmpty()!s2.isEmpty()){if(s1.peek()s2.peek()){return s1.peek();}else{s1.pop();s2.pop();}}return null;}public boolean getPath(TreeNode root,TreeNode target,StackTreeNode stack){if(rootnull) return false;stack.push(root);if(roottarget) return true;if(getPath(root.left,target,stack)){return true;}if(getPath(root.right,target,stack)){return true;}stack.pop();return false;}七、根据一棵树的前序遍历与中序遍历构造二叉树
给定两个整数数组 preorder 和 inorder 其中 preorder 是二叉树的先序遍历 inorder 是同一棵树的中序遍历请构造二叉树并返回其根节点。 根据一棵树的前序遍历与中序遍历构造二叉树 解题思路 1.定义一个buildTreeChild(int[] preorder, int[] inorder,int inbegin,int inend)方法用来构建二叉树int[] preorder前序遍历。 int[] inorder中序遍历。int inbegin标记中序遍历数组的起始位置。int inend标记中序遍历数组的末尾。 2.定义一个私有方法findVal(int[] inorder,int inbegin,int inend,int val)用来在中序遍历中找到根节点的位置。此时返回的int值左边的值就是左子树右边的值就是右子树。 public int preIndex0;public TreeNode buildTree(int[] preorder, int[] inorder) {return buildTreeChild(preorder,inorder,0,inorder.length-1);}public TreeNode buildTreeChild(int[] preorder, int[] inorder,int inbegin,int inend) {//这种情况下 表明 当前root 没有子树了 if(inbegin inend) {return null;}TreeNode root new TreeNode(preorder[preIndex]);int rootIndex findVal(inorder,inbegin,inend,preorder[preIndex]);preIndex;root.left buildTreeChild(preorder,inorder,inbegin,rootIndex-1);root.right buildTreeChild(preorder,inorder,rootIndex1,inend);return root;}private int findVal(int[] inorder,int inbegin,int inend,int val) {for(int i inbegin ;i inend;i) {if(inorder[i] val) {return i;}}return -1;}练习
根据一棵树的中序遍历与后序遍历构造二叉树
八、二叉树前序非递归遍历实现
给你二叉树的根节点 root 返回它节点值的 前序 遍历。 二叉树前序非递归遍历实现 解题思路 1.先判断root树是否为空。 2.定义一个栈和noderootnode开始往左遍历遍历一个将node.val放入链表中然后将node放入栈中当nodenull时nodestack.pop()遍历node右边的。 public ListInteger preorderTraversal(TreeNode root) {ListInteger listnew ArrayList();if(rootnull)return list;StackTreeNode stacknew Stack();TreeNode noderoot;while(node!null||!stack.isEmpty()) {while (node ! null) {list.add(node.val);stack.push(node);node node.left;}node stack.pop();node node.right;}return list;}练习
二叉树的中序遍历非递归
练习
二叉树的后序遍历非递归 此篇博客的全部代码
