查找北京国互网网站建设,制作企业网站教程,百度网站排名,搜索引擎优化工作主要做好哪些方面一、二叉树的翻转
1. 226【翻转二叉树】
题目#xff1a; 给你一棵二叉树的根节点 root #xff0c;翻转这棵二叉树#xff0c;并返回其根节点。代码#xff1a;
class Solution {public TreeNode invertTree(TreeNode root) {//翻转二叉树#xff0c;实际上就是交换左…一、二叉树的翻转
1. 226【翻转二叉树】
题目 给你一棵二叉树的根节点 root 翻转这棵二叉树并返回其根节点。代码
class Solution {public TreeNode invertTree(TreeNode root) {//翻转二叉树实际上就是交换左右结点//使用递归来交换根左右if(root null) return null;swapChildren(root);invertTree(root.left);invertTree(root.right);return root;}public void swapChildren(TreeNode root){TreeNode temp root.right;root.right root.left;root.left temp;}
}二、对称二叉树
1. 101 【对称二叉树】
题目 给你一个二叉树的根节点 root 检查它是否轴对称。代码
class Solution {public boolean isSymmetric(TreeNode root) {//对称二叉树对称的是根的左右子树//不能完全遍历左右子树之后比较遍历结果因为不能区分左结点或右结点为空的情况//左子树通过根左右的方式遍历//右子树通过根右左的方式遍历//若左右子树遍历的结果相同则是对称二叉树TreeNode left root.left;TreeNode right root.right;return inorder(left,right);}public boolean inorder(TreeNode left,TreeNode right){if(leftnull right!null) return false;if(left!null rightnull) return false;if(leftnull rightnull) return true;if(left.val ! right.val) return false;//前序遍历boolean f1 inorder(left.left,right.right);boolean f2 inorder(left.right,right.left);return f1f2;}
}2. 100【相同的树】
题目 给你两棵二叉树的根节点p和q编写一个函数来检验这两棵树是否相同。如果两个树在结构上相同并且节点具有相同的值则认为它们是相同的。代码
class Solution {public boolean isSameTree(TreeNode p, TreeNode q) {//递归遍历两棵树比较每个相应结点的值是否相等if(pnull q!null) return false;if(p!null qnull) return false;if(pnull qnull) return true;if(p.val ! q.val) return false;boolean f1 isSameTree(p.left,q.left);boolean f2 isSameTree(p.right,q.right);return f1f2;}
}三、二叉树的深度
1. 104【二叉树的最大深度】
题目 给定一个二叉树 root 返回其最大深度。二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。代码
class Solution {public int maxDepth(TreeNode root) {//求二叉树的深度本质上是遍历二叉树//上一篇有记录使用层序遍历求二叉树的深度//这里使用后序遍历求二叉树的深度if(root null) return 0;int leftDepth maxDepth(root.left);int rightDepth maxDepth(root.right);return 1Math.max(leftDepth,rightDepth);}
}2. 559【n叉树的最大深度】
题目 给定一个 n 叉树找到其最大深度。最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。代码
class Solution {public int maxDepth(Node root) {//这里同样用后序遍历来求解if(root null) return 0;int max 0;ListNode childNode root.children;for(Node n:childNode){max Math.max(max, maxDepth(n));}return 1max;}
}3. 111【二叉树的最小深度】
题目 给定一个二叉树找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。代码
class Solution {public int minDepth(TreeNode root) {//注意最小深度是根到叶子结点的最短距离//因此不能使用min(leftDepth,rightDepth)这样求得的不一定是到叶子结点的距离if (root null) return 0;int leftDepth minDepth(root.left);int rightDepth minDepth(root.right);if (root.left ! null root.right null) {return 1 leftDepth;}if (root.left null root.right ! null) {return 1 rightDepth;} else {return 1 Math.min(leftDepth, rightDepth);}}
}4. 222【完全二叉树的节点个数】
题目 给你一棵完全二叉树的根节点 root 求出该树的节点个数。 完全二叉树的定义如下在完全二叉树中除了最底层节点可能没填满外其余每层节点数都达到最大值并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层则该层包含 1 − 2 h 1 - 2^h 1−2h 个节点。代码
class Solution {public int countNodes(TreeNode root) {//将完全二叉树划分为多个满二叉树求每个满二叉树的节点个数//完全二叉树如果最左边的节点个数最右边节点个数则是一个满二叉树//满二叉树的节点个数2^n-1n是树的深度if(root null) return 0;int leftNum 0;int rightNum 0;TreeNode tempNode root;while(tempNode.left ! null){leftNum;tempNode tempNode.left;}tempNode root;while (tempNode.right ! null){rightNum;tempNode tempNode.right;}if(leftNum rightNum){return (2rightNum)-1;}else{int leftDepth countNodes(root.left);int rightDepth countNodes(root.right);return leftDepthrightDepth1;}}
}5. 110【平衡二叉树】
题目 给定一个二叉树判断它是否是高度平衡的二叉树。代码
class Solution {public int getHeight(TreeNode node){//该题不可以简单的使用最大深度-最小深度1来判断//如果一棵树只有一条路径则最大深度-最小深度01//但它不一定是平衡的if(node null) return 0;int leftHeight getHeight(node.left);int rightHeight getHeight(node.right);if(leftHeight-1 || rightHeight-1){return -1;}//左右子树高度相差1或0都可以if(Math.abs(leftHeight-rightHeight) 1){return -1;}return 1Math.max(leftHeight,rightHeight);}public boolean isBalanced(TreeNode root) {//平衡二叉树每个节点的左右子树高度差的绝对值不超过1//计算左右子树的高度然后计算高度差的绝对值是否为1if(getHeight(root)!-1){return true;} else {return false;}}
}
