网站建设外包公司容易被客户投诉吗,做游戏代练的网站,亿动广告公司,网站想改版 权重目录
1. 题目1#xff1a;检查两棵树是否相同 2. 题目2#xff1a;判断一棵树是否为另一棵树的子树
3. 题目3#xff1a;翻转二叉树
4. 题目4#xff1a;判断一棵树是否为平衡二叉树
5. 题目5#xff1a;判断一棵树是否为对称二叉树
6. 题目6#xff1a;二叉树的层序…目录
1. 题目1检查两棵树是否相同 2. 题目2判断一棵树是否为另一棵树的子树
3. 题目3翻转二叉树
4. 题目4判断一棵树是否为平衡二叉树
5. 题目5判断一棵树是否为对称二叉树
6. 题目6二叉树的层序遍历
7. 题目7二叉树的遍历
8. 题目8二叉树的最近公共祖先
9. 题目9根据前序与中序遍历构造二叉树
10. 题目10根据中序与后序遍历构造二叉树
11. 题目11根据二叉树创建字符串
12. 题目12非递归实现二叉树前序遍历
13. 题目13非递归实现二叉树中序遍历
14. 题目14非递归实现二叉树后序遍历 1. 题目1检查两棵树是否相同
题目链接100. 相同的树 - 力扣LeetCode
解题思路递归思路判断根节点是否相同左子树是否相同右子树是否相同
相同判定有两方面结构与数值
代码
class Solution {public boolean isSameTree(TreeNode p, TreeNode q) {// 两树均为空if(p null q null){return true;}// 两树一空一非空if((p null q ! null)||(p ! null q null)){return false;}// 两树均不为空// 两树根节点数据域值不同if(p.val ! q.val){return false;}// 两树根节点数据域值相同return isSameTree(p.left,q.left) isSameTree(p.right, q.right);}
}
时间复杂度O(min(m,n))其中mn分别为两棵树的结点数 2. 题目2判断一棵树是否为另一棵树的子树
题目链接572. 另一棵树的子树 - 力扣LeetCode
解题思路判断两棵树是否相同递归判断一棵是否为另一棵的左子树是否为其右子树
代码
class Solution {public boolean isSameTree(TreeNode p, TreeNode q){if(p null q null){return true;}if((p null q ! null) || (p ! null q null)){return false;}if(p.val ! q.val){return false;}return isSameTree(p.left, q.left) isSameTree(p.right, q.right);}public boolean isSubtree(TreeNode root, TreeNode subRoot) {if(root null || subRoot null){return false;}if(isSameTree(root, subRoot)){return true;}if(isSubtree(root.left,subRoot)){return true;}if(isSubtree(root.right, subRoot)){return true;}return false;}
}
时间复杂度O(s * t)
3. 题目3翻转二叉树
题目链接226. 翻转二叉树 - 力扣LeetCode
解题思路在二叉树不为空时将二叉树的左右子树交换再递归交换左子树的左右子树和右子树的左右子树
代码
class Solution {public TreeNode invertTree(TreeNode root) {if(root null){return null;}TreeNode tmp root.left;root.left root.right;root.right tmp;invertTree(root.left);invertTree(root.right);return root;}
}
4. 题目4判断一棵树是否为平衡二叉树
题目链接110. 平衡二叉树 - 力扣LeetCode
解题思路
代码1
class Solution {public boolean isBalanced(TreeNode root) {if(root null){return true;}int leftH maxDepth(root.left);int rightH maxDepth(root.right);return Math.abs(leftH - rightH) 2 isBalanced(root.left) isBalanced(root.right);}public int maxDepth(TreeNode root){if(root null){return 0;}int leftHeight maxDepth(root.left);int rightHeight maxDepth(root.right);return (leftHeightrightHeight)?(leftHeight1):(rightHeight1);}
}
时间复杂度O(N²)
代码2
class Solution {public boolean isBalanced(TreeNode root) {return maxDepth(root) 0;}public int maxDepth(TreeNode root){if(root null){return 0;}int leftHeight maxDepth(root.left);if(leftHeight 0){return -1;}int rightHeight maxDepth(root.right);if(rightHeight 0){return -1;}if(Math.abs(leftHeight - rightHeight) 1){return Math.max(leftHeight,rightHeight)1;}else{return -1;}}
}
时间复杂度ON
5. 题目5判断一棵树是否为对称二叉树
题目链接101. 对称二叉树 - 力扣LeetCode
代码
class Solution {public boolean isSymmetric(TreeNode root) {if(root null){return true;}// 判断左子树的左树 和 右子树的右树是否对称return isSymmetricChild(root.left,root.right);}public boolean isSymmetricChild(TreeNode leftTree, TreeNode rightTree){if(leftTree null rightTree null){return true;}if((leftTree null rightTree ! null)||(leftTree ! null rightTree null)){return false;}// 左右子树均不为空// 左右子树根节点数据不同if(leftTree.val ! rightTree.val){return false;}// 左右子树根节点数据相同return isSymmetricChild(leftTree.left,rightTree.right) isSymmetricChild(leftTree.right, rightTree.left);}
}
6. 题目6二叉树的层序遍历
题目链接102. 二叉树的层序遍历 - 力扣LeetCode
代码
class Solution {public ListListInteger levelOrder(TreeNode root) {ListListInteger list new ArrayList();if(root null){return list;}QueueTreeNode queue new LinkedList();queue.offer(root);while(!queue.isEmpty()){int size queue.size();ListInteger tmp new ArrayList();while(size ! 0){TreeNode cur queue.poll();tmp.add(cur.val);size--;if(cur.left ! null){queue.offer(cur.left);}if(cur.right ! null){queue.offer(cur.right);}}list.add(tmp);}return list;}
}
7. 题目7二叉树的遍历
题目链接二叉树遍历_牛客题霸_牛客网
代码
import java.util.Scanner;
class TreeNode{public char val;public TreeNode left;public TreeNode right;public TreeNode(char val){this.val val;}
}
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 casei0; // 将i置为0防止多组测试i累加String str in.nextLine();TreeNode root createTree(str);inOrder(root);}}public static int i 0;public static TreeNode createTree(String str){TreeNode root null;if(str.charAt(i)!#){// 遍历字符串不为空的字符创建结点root new TreeNode(str.charAt(i));i;root.left createTree(str);root.right createTree(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);}
}
8. 题目8二叉树的最近公共祖先
题目链接236. 二叉树的最近公共祖先 - 力扣LeetCode
解题思路
方法1除过空树与pq二者之一为根结点的情况外分为三种情况第一种pq分别在根的左右两边第二种pq都在根的左边或右边第三种pq中有一个结点是公共祖先
代码 public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q){if(root null){return null;}if(p root || q root){return root;}// 分别在根结点的左右子树查找目标结点TreeNode leftRet lowestCommonAncestor(root.left, p, q);TreeNode rightRet lowestCommonAncestor(root.right, p, q);// 第一种情况左右子树均有目标结点则根结点为公共祖先if(leftRet ! null rightRet ! null){return root;}else if(leftRet ! null){// 第二种情况 右子树没有查询到目标结点两个目标结点均在左子树return leftRet;// leftRet已经记录了左子树查询到的第一个目标结点// 同时由于2个目标结点均在左子树即已经记录到的leftRet即是两个结点的最近公共祖先}else if(rightRet ! null){// 左子树没有查询到目标结点两个目标结点均在右子树return rightRet;// 同第一个else-if语句rightRet即是2个目标结点的最近公共祖先}return null;}
方法2建两个栈分别存储pq两结点从根结点开始途径的每一个结点从结点多的栈开始出栈从两个栈元素数量相同开始两个栈同时弹出栈顶元素进行比较是否相同相同则是公共祖先不相同则依次比较下一个元素
代码
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {// 建2个栈分别用于存放根结点root到目标结点p与q的路径结点DequeTreeNode stack1 new LinkedList();getPath(root, p, stack1);DequeTreeNode stack2 new LinkedList();getPath(root, q, stack2);// 判断栈大小先出栈元素多的栈直至与另一个栈元素个数相同两栈开始同时出栈元素int size1 stack1.size();int size2 stack2.size();if(size1 size2){int size size1 - size2;while(size ! 0){stack1.pop();size--;}}else{int size size2 - size1;while(size ! 0){stack2.pop();size--;}}// 此时两栈元素个数已经相同// 当两个栈均不为空时逐个元素对比while(!stack1.isEmpty() !stack2.isEmpty()){// 两栈栈顶元素不同则同时出栈if(stack1.peek() ! stack2.peek()){stack1.pop();stack2.pop();}else{// 两栈栈顶元素相同该结点为公共祖先return stack1.peek();}}return null;}public boolean getPath(TreeNode root, TreeNode node, DequeTreeNode stack){// 查找从根结点root到目标结点node路径上的结点并存放到栈stack中if(root null || node null){return false;}// 将当前结点入栈stack.push(root);// 判断该结点是否为目标结点if(root node){return true;}// 判断该结点左子树中是否有目标结点boolean ret1 getPath(root.left, node, stack);if(ret1 true){return true;}// 判断该结点右子树中是否有目标结点boolean ret2 getPath(root.right, node, stack);if(ret2 true){return true;}// 左右子树均查询无果则出栈该结点并返回空stack.pop();return false;}
}
注如果二叉树每个结点中存储了其父亲结点的地址则改题等效于求两个链表的交叉结点问题
9. 题目9根据前序与中序遍历构造二叉树
题目链接105. 从前序与中序遍历序列构造二叉树 - 力扣LeetCode
代码
class Solution {public int i0; //用于前序preorder遍历public TreeNode buildTree(int[] preorder, int[] inorder) {return buildTreeChild(preorder, inorder, 0,inorder.length-1);}public TreeNode buildTreeChild(int[] preorder, int[] inorder, int inBgein, int inEnd){if(inBgein inEnd){ // 没有子树return null;}TreeNode root new TreeNode(preorder[i]); // root结点// 在中序遍历inorder中定位根结点root位置int rootIndex findIndex(inorder, inBgein, inEnd, preorder[i]);i;// 在中序遍历中确定根结点位置后其左为左树右为右树root.left buildTreeChild(preorder, inorder, inBgein, rootIndex-1);root.right buildTreeChild(preorder, inorder, rootIndex1, inEnd);return root;}private int findIndex(int[] inorder, int inBgein, int inEnd, int key){for(int iinBgein; i inEnd;i){if(inorder[i] key){return i;}}return -1;}
}
10. 题目10根据中序与后序遍历构造二叉树
题目链接106. 从中序与后序遍历序列构造二叉树 - 力扣LeetCode
代码
class Solution {public int i 0;public TreeNode buildTree(int[] inorder, int[] postorder) {i inorder.length-1;return buildTreeChild(postorder, inorder, 0, inorder.length-1);}public TreeNode buildTreeChild(int[] postorder, int[] inorder, int inBegin, int inEnd){if(inBegin inEnd){return null;}TreeNode root new TreeNode(postorder[i]);int rootIndex findIndex(inorder, inBegin, inEnd, postorder[i]);i--;root.right buildTreeChild(postorder, inorder, rootIndex1, inEnd);root.left buildTreeChild(postorder, inorder, inBegin, rootIndex-1);return root;}private int findIndex(int[] inorder, int inBegin, int inEnd, int key){for(int jinBegin;jinEnd;j){if(inorder[j] key){return j;}}return -1;}
}
11. 题目11根据二叉树创建字符串
题目链接606. 根据二叉树创建字符串 - 力扣LeetCode
解题思路分为以下三种情况1结点左右均为空直接返回2结点左不为空右为空无需为空结点增加括号3结点左空右不为空给空结点增加括号
代码
class Solution {public String tree2str(TreeNode root) {if(root null){return null;}StringBuilder stringBuilder new StringBuilder();tree2strChild(root, stringBuilder);return stringBuilder.toString();}public void tree2strChild(TreeNode node, StringBuilder stringBuilder){if(node null){return;}stringBuilder.append(node.val);// 判断结点左子树if(node.left ! null){// 结点左孩子不为空stringBuilder.append(();tree2strChild(node.left, stringBuilder);stringBuilder.append());}else{// 结点左孩子为空// 情况1结点右孩子不为空if(node.right ! null){stringBuilder.append(());}else{// 情况2结点右孩子为空return;}}// 判断结点右子树if(node.right null){// 结点右孩子为空直接返回return;}else{// 结点右孩子不为空递归结点的右子树stringBuilder.append(();tree2strChild(node.right, stringBuilder);stringBuilder.append());}}
}
12. 题目12非递归实现二叉树前序遍历
题目链接144. 二叉树的前序遍历 - 力扣LeetCode
代码
class Solution {public ListInteger preorderTraversal(TreeNode root) {ListInteger ret new ArrayList();if(root null){return ret;}TreeNode cur root; // 用于遍历二叉树DequeTreeNode stack new ArrayDeque();while(cur ! null || !stack.isEmpty()){while(cur ! null){stack.push(cur);ret.add(cur.val);cur cur.left;}TreeNode top stack.pop();cur top.right;}return ret;}
}
13. 题目13非递归实现二叉树中序遍历
题目链接94. 二叉树的中序遍历 - 力扣LeetCode
代码
class Solution {public ListInteger inorderTraversal(TreeNode root) {ListInteger ret new ArrayList();if(root null){return ret;}TreeNode cur root;DequeTreeNode stack new ArrayDeque();while(cur ! null || !stack.isEmpty()){while(cur ! null){stack.push(cur);cur cur.left;}TreeNode top stack.pop();ret.add(top.val);cur top.right;}return ret;}
}
14. 题目14非递归实现二叉树后序遍历
题目链接145. 二叉树的后序遍历 - 力扣LeetCode
代码
class Solution {public ListInteger postorderTraversal(TreeNode root) {ListInteger ret new ArrayList();if(root null){return ret;}TreeNode cur root;TreeNode prev null;DequeTreeNode stack new ArrayDeque();while(cur ! null || !stack.isEmpty()){while(cur ! null){stack.push(cur);cur cur.left;}// 后序遍历顺序为根-左-右TreeNode top stack.peek(); // 不可以直接pop栈顶元素// 当栈顶元素结点没有右子树时才可以打印根结点if(top.right null || top.right prev){ret.add(top.val);stack.pop();prev top;}else{// 栈顶元素结点有右子树优先遍历右子树后再打印根结点cur top.right;}}return ret;}
}
