当前位置：首页 > news >正文

二叉树的算法题目

news 来源：原创 2024/9/29 21:32:21

二叉树的遍历题目

二叉树遍历一般包含三种分别为：根左右、左根右、左右根（又称为前序遍历、中序遍历、后序遍历）

方法一：使用递归遍历方法二：使用迭代使用栈

我们以左根右（中序遍历）为例：下列代码中，我们在遍历题目中我们展示方法二，用来存储我们的运行过程中访问到的结点。

第一个while如果根结点不是空或者栈不是空的，我们就循环执行
第二while，当根结点不为空时，把结点放到我们的栈中，并访问根的左子树
当没有左子树可访问后，提取出栈的最后一个进入的子树
把该子树放到列表中
然后再访问该结点的右子树，（但是由于该结点没有右子树时，这重新进入循环，重复1-5这些步骤）

上述步骤如有不清楚，可以参考下图卡片链接视频，视频第9分钟的时候

1-024-_(LeetCode-94) 二叉树的中序遍历_哔哩哔哩_bilibilihttps://www.bilibili.com/video/BV1eg411w7gn?p=25&vd_source=6d86118bce41ec0856a5d50f6c17a7e7上述代码，无论是前中后序遍历，只要将res.add(root.val)移动一下位置即可，在前序中，把该代码反到循环内，在每次访问根节点的时候，直接将根节点的值放到res中；

而后序则是完全不一样，由于在访问结点过程中先访问左结点后，必须访问右结点（除没有右节点外），所以在出栈后的结点，需查找它的右节点，找到好先对右节点进行排序，最后再排出栈的结点。所以其算法编写为：

class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();Deque<TreeNode> stack = new LinkedList<>();TreeNode prevAccess = null;while(root!=null || !stack.isEmpty()){while(root!=null){stack.push(root);root = root.left;}root = stack.pop();if(root.right == null || root.right == prevAccess){res.add(root.val);prevAccess = root;root =null;}else{stack.push(root);root = root.right;}}return res;}
}

若有不懂得题目，可以点击下面卡片链接1-026-(LeetCode-145) 二叉树的后序遍历_哔哩哔哩_bilibilihttps://www.bilibili.com/video/BV1eg411w7gn?p=27&vd_source=6d86118bce41ec0856a5d50f6c17a7e7

二叉树镜像对称题目

解决方法一：定义一个递归方法，循环遍历左子树的左孩子和右子树的右孩子进行比较，在比较左右孩子和右左孩子

/*** 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;*     }* }*/
class Solution {public boolean isSymmetric(TreeNode root) {if(root == null){return true;}return deepCheck(root.left,root.right);}boolean deepCheck(TreeNode left, TreeNode right){if(left==null && right==null){return true;}if(left==null || right==null){return false;}if(left.val != right.val){return false;}return deepCheck(left.left,right.right)&& deepCheck(left.right,right.left);}
}

方法二：循环迭代的方法，这里用到了队列

这里可以看下面卡片第三分钟有所介绍：1-027-(LeetCode-101) 对称二叉树_哔哩哔哩_bilibilihttps://www.bilibili.com/video/BV1eg411w7gn?p=28&vd_source=6d86118bce41ec0856a5d50f6c17a7e7

public class Soultion {pubilic boolean isSymmetric(TreeNode root) {Queue<TreeNode> q = new LinkedList<TreeNode>();TreeNode u = root.left;TreeNode v = root.right;if(root == null|| (u == null && v == null)){return true;}//入队q.offer(u);q.offer(v);while(!q.isEmpty()){//队列取出操作u = q.poll();v = q.poll();while (!q.isEmpty()){u = q.poll();v = q.poll();if(u == null && v == null){continue;}if((u==null|| v==null) ||(u.val! = v.val)){return false;}q.offer(u.left);q.offer(v.right);q.offer(u.right);q.offer(v.left);}return true;}}
}

二叉树最大深度算法问题

方法一：递归解决方法

/*** 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;*     }* }*/
class Solution {public int maxDepth(TreeNode root) {if(root == null){return 0;}else{return Math.max(maxDepth(root.left),maxDepth(root.right))+1;}}
}

方法二：迭代循环方法，这里仍然用到队列

public class Soultion {public int maxDepthWithQueue(TreeNode root) {if(root == null){return 0;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);int depth = 0;while (!queue.isEmpty()) {//size记录本层的结点是否全部解决完int size = queue.size();while(size>0){TreeNode node = queue.poll();if (node.left!= null) {queue.offer(node.left);}if (node.right!= null) {queue.offer(node.right);}size--;}depth++;}return depth;}
}

一分43秒

1-028-(LeetCode-104) 二叉树的最大深度_哔哩哔哩_bilibilihttps://www.bilibili.com/video/BV1eg411w7gn?p=29&vd_source=6d86118bce41ec0856a5d50f6c17a7e7

平衡二叉树题目

什么是平衡二叉树：一个二叉树每个结点的左右两个子树的高度差的绝对值不超过1。

用递归方式实现：

/*** 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;*     }* }*/
class Solution {public boolean isBalanced(TreeNode root) {if(root == null){return true;}//调用递归方法return helper(root)!=-1;}public int helper(TreeNode root){if(root==null){return 0 ;}//统计左右子树的高度int left = helper(root.left);int right = helper(root.right);//比较if(left == -1 || right == -1 || Math.abs(left - right)>1){return -1;}return Math.max(left,right)+1;}
}

翻转二叉树题目

用递归的形式解题

/*** 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;*     }* }*/
class Solution {public TreeNode invertTree(TreeNode root) {if(root == null){return null;}//翻转根结点的左孩子invertTree(root.left);//翻转根结点的右孩子invertTree(root.right);TreeNode temp = root.left;//然后左右孩子交换root.left= root.right;root.right =temp;return root;}
}