目录
前言
此篇是对二叉树的练习，一些比较基础的题！
一、相同的树
1.1 题解
方法：深度优先搜索
如果两个二叉树都为空，则两个二叉树相同。如果两个二叉树中有且只有一个为空，则两个二叉树一定不相同。
如果两个二叉树都不为空，那么首先判断它们的根节点的值是否相同，若不相同则两个二叉树一定不同，若相同，再分别判断两个二叉树的左子树是否相同以及右子树是否相同。这是一个递归的过程，因此可以使用深度优先搜索，递归地判断两个二叉树是否相同。
1.2 代码实现
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/classSolution{publicbooleanisSameTree(TreeNode p,TreeNode q){if(p ==null&& q !=null|| p !=null&& q ==null){returnfalse;}if(p ==null&& q ==null){returntrue;}if(p.val != q.val){returnfalse;}returnisSameTree(p.left,q.left)&&isSameTree(p.right,q.right);}}
二、另一颗树的子树
2.1 题解
方法：深度优先搜索暴力匹配
先判断二者是否为空，都为空返回false。子树可能是父树的左子树或右子树，如果都不满足返回false。
2.2 代码实现
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/classSolution{publicbooleanisSameTree(TreeNode p,TreeNode q){if(p ==null&& q !=null|| p !=null&& q ==null){returnfalse;}if(p ==null&& q ==null){returntrue;}if(p.val != q.val){returnfalse;}returnisSameTree(p.left,q.left)&&isSameTree(p.right,q.right);}publicbooleanisSubtree(TreeNode root,TreeNode subRoot){if(root ==null|| subRoot ==null){returnfalse;}if(isSameTree(root, subRoot)){returntrue;}if(isSubtree(root.left, subRoot)){returntrue;}if(isSubtree(root.right, subRoot)){returntrue;}returnfalse;}}
三、二叉树的最大深度
3.1 题解
方法：深度优先搜索
二叉树的最大深度无非就是左子树和右子树的最大深度+1，二叉树根节点为null的话，返回0。
3.2 代码实现
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/classSolution{publicintmaxDepth(TreeNode root){if(root ==null){return0;}int leftHeight =maxDepth(root.left);int rightHeight =maxDepth(root.right);return leftHeight > rightHeight ? leftHeight+1: rightHeight+1;}}
四、二叉树的前序遍历
4.1 题解
方法：递归
每访问到一个节点如何给它存起来，那么我们定义一个顺序表来存储！
4.2 代码实现
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/classSolution{publicList<Integer>preorderTraversal(TreeNode root){List<Integer> retlist =newArrayList<>();if(root ==null){return retlist;}
retlist.add(root.val);List<Integer> leftTree =preorderTraversal(root.left);
retlist.addAll(leftTree);List<Integer> rightTree =preorderTraversal(root.right);
retlist.addAll(rightTree);return retlist;}}
五、二叉树的中序遍历
5.1 题解
方法：递归
同上题。
5.2 代码实现
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/classSolution{publicList<Integer>inorderTraversal(TreeNode root){List<Integer> retlist =newArrayList<>();if(root ==null){return retlist;}List<Integer> leftTree =inorderTraversal(root.left);
retlist.addAll(leftTree);
retlist.add(root.val);List<Integer> rightTree =inorderTraversal(root.right);
retlist.addAll(rightTree);return retlist;}}
六、二叉树的后序遍历
6.1 题解
方法：递归
同上题。
6.2 代码实现
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/classSolution{publicList<Integer>postorderTraversal(TreeNode root){List<Integer> retlist =newArrayList<>();if(root ==null){return retlist;}List<Integer> leftTree =postorderTraversal(root.left);
retlist.addAll(leftTree);List<Integer> rightTree =postorderTraversal(root.right);
retlist.addAll(rightTree);
retlist.add(root.val);return retlist;}}
七、平衡二叉树
7.1 题解
方法一：自顶向下递归
具体做法类似于二叉树的前序遍历，即对于当前遍历到的节点，首先计算左右子树的高度，如果左右子树的高度差是否不超过 1，再分别递归地遍历左右子节点，并判断左子树和右子树是否平衡。
方法二：自低向上递归
方法一由于是自顶向下递归，因此对于同一个节点，函数 height 会被重复调用，导致时间复杂度较高。如果使用自底向上的做法，则对于每个节点，函数 height 只会被调用一次。
自底向上递归的做法类似于后序遍历，对于当前遍历到的节点，先递归地判断其左右子树是否平衡，再判断以当前节点为根的子树是否平衡。如果一棵子树是平衡的，则返回其高度（高度一定是非负整数），否则返回 -1。如果存在一棵子树不平衡，则整个二叉树一定不平衡。
7.2 代码实现
方法一：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*//**
* 求树的高度
* @param root
* @return
*///时间复杂度：O(n)publicintheight(TreeNode root){if(root ==null)return0;int leftHeight =height(root.left);int rightHeight =height(root.right);return(leftHeight > rightHeight)?(leftHeight+1):(rightHeight+1);}/**
* 平衡二叉树
* @param root
* @return
*///时间复杂度：O(N^2)publicbooleanisBalanced(TreeNode root){if(root ==null)returntrue;int left =height(root.left);int right =height(root.right);returnMath.abs(left-right)<=1&&isBalanced(root.left)&&isBalanced(root.right);}
方法二：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/classSolution{//时间复杂度：O(n)publicintheight(TreeNode root){if(root ==null)return0;int leftHeight =height(root.left);int rightHeight =height(root.right);if(leftHeight >=0&& rightHeight >=0&&Math.abs(leftHeight-rightHeight)<=1){returnMath.max(leftHeight,rightHeight)+1;}else{//说明不平衡return-1;}}//时间复杂度：O(N)publicbooleanisBalanced(TreeNode root){if(root ==null)returntrue;returnheight(root)>=0;}}
八、对称二叉树
8.1 题解
方法：递归
树根为空，返回true，左右子树都为null，返回true，判断左子树和右子树的值是否相同，否则直接返回false，递归判断左子树的左树和右子树的右树，左子树的右树和右子树的左树是否相同。
8.2 代码实现
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/classSolution{publicbooleanisSymmetric(TreeNode leftTree,TreeNode rightTree){if(leftTree ==null&& rightTree !=null)returnfalse;if(leftTree !=null&& rightTree ==null)returnfalse;if(leftTree ==null&& rightTree ==null)returntrue;if(leftTree.val != rightTree.val)returnfalse;returnisSymmetric(leftTree.left, rightTree.right)&&isSymmetric(leftTree.right, rightTree.left);}publicbooleanisSymmetric(TreeNode root){if(root ==null)returntrue;returnisSymmetric(root.left, root.right);}}
本文转载自: https://blog.csdn.net/weixin_61341342/article/details/127337761
版权归原作者 摸鱼王胖嘟嘟 所有， 如有侵权，请联系我们删除。
版权归原作者 摸鱼王胖嘟嘟 所有， 如有侵权，请联系我们删除。