Letcode-Top 100二叉树专题

2024-06-10 04:28
文章标签 二叉树 100 top 专题 letcode

本文主要是介绍Letcode-Top 100二叉树专题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

94. 二叉树的中序遍历

在这里插入图片描述
方法一：递归法

/*** 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 List<Integer> inorderTraversal(TreeNode root) {List<Integer> arraylist=new ArrayList<>();if(root==null){return arraylist;}Stack<TreeNode> stack=new Stack<TreeNode>();TreeNode current=root;while(current!=null||!stack.isEmpty()){while(current!=null){stack.push(current);current=current.left;}current=stack.pop();arraylist.add(current.val);current=current.right;}return arraylist;}
}

方法二：迭代法

/*** 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 List<Integer> inorderTraversal(TreeNode root) {// 中序遍历List<Integer> res = new ArrayList<Integer>();inorderTraversal(root, res);return res;}public void inorderTraversal(TreeNode node, List<Integer> res) {if (node == null) {return;}inorderTraversal(node.left, res);res.add(node.val);inorderTraversal(node.right, res);}}

104. 二叉树的最大深度

在这里插入图片描述
方法一：递归方法

/*** 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 {int leftLength = maxDepth(root.left)+1;int rightLength = maxDepth(root.right)+1;return Math.max(leftLength,rightLength);}}
}

方法二：层序遍历

class Solution {public int maxDepth(TreeNode root) {if (root == null) {return 0;}int ans = 0;int size = 0;LinkedList<TreeNode> queue = new LinkedList<TreeNode>();queue.add(root);while (!queue.isEmpty()) {size = queue.size();while (size > 0) {root = queue.poll();if (root.left != null) {queue.offer(root.left);}if (root.right != null) {queue.offer(root.right);}size--;}ans++;}return ans;}
}

226. 翻转二叉树

在这里插入图片描述
方法一：递归

/*** 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 {int leftLength = maxDepth(root.left)+1;int rightLength = maxDepth(root.right)+1;return Math.max(leftLength,rightLength);}}
}

方法二：迭代

class Solution {public TreeNode invertTree(TreeNode root) {if (root == null) {return null;}TreeNode node = root;Queue<TreeNode> queue = new LinkedList<TreeNode>();queue.add(node);int size = 0;while (!queue.isEmpty()) {size = queue.size();while (size > 0) {TreeNode temp = queue.poll();TreeNode left = temp.left;if (left != null) {queue.offer(left);}TreeNode right = temp.right;if (right != null) {queue.offer(right);}temp.left = right;temp.right = left;size--;}}return root;}
}

101. 对称二叉树

在这里插入图片描述
方法一：递归

/*** 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 isSymmetric(root.left,root.right);}public boolean isSymmetric(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 isSymmetric(left.left,right.right)&& isSymmetric(left.right,right.left);}}

方法二：迭代

class Solution {public boolean isSymmetric(TreeNode root) {if (root == null) {return true;}return isSymmetric(root.left, root.right);}public boolean isSymmetric(TreeNode left, TreeNode right) {Queue<TreeNode> queue = new LinkedList<TreeNode>();queue.offer(left);queue.offer(right);while (!queue.isEmpty()) {left = queue.poll();right = queue.poll();if (left == null && right == null) {continue;}if (left == null || right == null || left.val != right.val) {return false;}queue.offer(left.left);queue.offer(right.right);queue.offer(left.right);queue.offer(right.left);}return true;}}

543. 二叉树的直径

在这里插入图片描述
方法一：递归

class Solution {int ans = 0;public int diameterOfBinaryTree(TreeNode root) {diameterOfBinaryTreePLus(root);return ans;}public int diameterOfBinaryTreePLus(TreeNode root) {if(root==null){return 0;}int left =  diameterOfBinaryTreePLus(root.left);int right = diameterOfBinaryTreePLus(root.right);ans = Math.max(ans,left+right);return Math.max(left+1,right+1);}
}

102. 二叉树的层序遍历

在这里插入图片描述

class Solution {public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> result = new ArrayList<List<Integer>>();if (root == null) {return result;}Queue<TreeNode> queue = new LinkedList<TreeNode>();queue.offer(root);int size = 0;while (!queue.isEmpty()) {size = queue.size();List<Integer> list = new ArrayList<Integer>();while (size > 0) {TreeNode node = queue.poll();list.add(node.val);if (node.left != null) {queue.offer(node.left);}if (node.right != null) {queue.offer(node.right);}size--;if (size == 0) {result.add(list);}}}return result;}
}

108. 将有序数组转换为二叉搜索树

在这里插入图片描述

class Solution {public TreeNode sortedArrayToBST(int[] nums) {return sortedArrayToBST(nums,0,nums.length-1);}public TreeNode sortedArrayToBST(int[] nums,int left,int right){if(left>right){return null;}int mid = (left+right)/2;TreeNode root = new TreeNode(nums[mid]);root.left =  sortedArrayToBST(nums,left,mid-1);root.right = sortedArrayToBST(nums,mid+1,right);return root;}
}

98. 验证二叉搜索树

在这里插入图片描述
方法一：递归

初始错误写法

class Solution {public boolean isValidBST(TreeNode root) {if (root == null) {return true;}if (root.left != null) {if (root.left.val >= root.val) {return false;}}if (root.right != null) {if (root.right.val <= root.val) {return false;}}boolean left = isValidBST(root.left);boolean right = isValidBST(root.right);return left && right;}
}

在这里插入图片描述
正确写法

/*** Definition for a binary tree node.* public class TreeNode {* long val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(long val) { this.val = val; }* TreeNode(long val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {public boolean isValidBST(TreeNode root) {if (root == null) {return true;}return isValidBSTPlus(root,Long.MIN_VALUE,Long.MAX_VALUE);}public boolean isValidBSTPlus(TreeNode root,long min,long max) {if (root == null) {return true;}if (root.left != null) {if (root.left.val >= root.val) {return false;}}if (root.right != null) {if (root.right.val <= root.val) {return false;}}if(root.val>=max || root.val<=min){return false;}boolean left = isValidBSTPlus(root.left,min,root.val);boolean right = isValidBSTPlus(root.right,root.val,max);return left && 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;* }* }*/
class Solution {public boolean isValidBST(TreeNode root) {long limit = Long.MIN_VALUE;Stack<TreeNode> stack = new Stack<TreeNode>();TreeNode currentNode = root;while (currentNode != null || !stack.isEmpty()) {while (currentNode != null) {stack.push(currentNode);currentNode = currentNode.left;}currentNode = stack.pop();if (currentNode.val <= limit) {return false;}limit = currentNode.val;currentNode = currentNode.right;}return true;}
}

这篇关于Letcode-Top 100二叉树专题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1047205。

相关文章

【专题】2024飞行汽车技术全景报告合集PDF分享（附原数据表）

【专题】2024飞行汽车技术全景报告合集PDF分享（附原数据表）

原文链接： https://tecdat.cn/?p=37628 6月16日，小鹏汇天旅航者X2在北京大兴国际机场临空经济区完成首飞，这也是小鹏汇天的产品在京津冀地区进行的首次飞行。小鹏汇天方面还表示，公司准备量产，并计划今年四季度开启预售小鹏汇天分体式飞行汽车，探索分体式飞行汽车城际通勤。阅读原文，获取专题报告合集全文，解锁文末271份飞行汽车相关行业研究报告。 据悉，业内人士对飞行汽车行业
阅读更多...
leetcode105 从前序与中序遍历序列构造二叉树

leetcode105 从前序与中序遍历序列构造二叉树

根据一棵树的前序遍历与中序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如，给出 前序遍历 preorder = [3,9,20,15,7]中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树： 3/ \9 20/ \15 7   class Solution {public TreeNode buildTree(int[] pr
阅读更多...
音视频入门基础：WAV专题（10）——FFmpeg源码中计算WAV音频文件每个packet的pts、dts的实现

音视频入门基础：WAV专题（10）——FFmpeg源码中计算WAV音频文件每个packet的pts、dts的实现

一、引言 从文章《音视频入门基础：WAV专题（6）——通过FFprobe显示WAV音频文件每个数据包的信息》中我们可以知道，通过FFprobe命令可以打印WAV音频文件每个packet（也称为数据包或多媒体包）的信息，这些信息包含该packet的pts、dts： 打印出来的“pts”实际是AVPacket结构体中的成员变量pts，是以AVStream->time_base为单位的显
阅读更多...
PHP实现二叉树遍历(非递归方式，栈模拟实现)

PHP实现二叉树遍历(非递归方式，栈模拟实现)

二叉树定义是这样的：一棵非空的二叉树由根结点及左、右子树这三个基本部分组成，根据节点的访问位置不同有三种遍历方式： ① NLR：前序遍历(PreorderTraversal亦称(先序遍历)) ——访问结点的操作发生在遍历其左右子树之前。 ② LNR：中序遍历(InorderTraversal) ——访问结点的操作发生在遍历其左右子树之中(间)。 ③ LRN：后序遍历(PostorderT
阅读更多...
专题二_滑动窗口_算法专题详细总结

专题二_滑动窗口_算法专题详细总结

目录 滑动窗口，引入： 滑动窗口，本质：就是同向双指针； 1.⻓度最⼩的⼦数组（medium） 1.解析：给我们一个数组nums，要我们找出最小子数组的和==target，首先想到的就是暴力解法 1）暴力： 2）优化，滑动窗口: 1.进窗口 2.出窗口 3.更新值 2.⽆重复字符的最⻓⼦串（medium） 1）仍然是暴力解法： 2）优化： 进窗口：hash[s[rig
阅读更多...
【LeetCode热题100】前缀和

【LeetCode热题100】前缀和

这篇博客共记录了8道前缀和算法相关的题目，分别是：【模版】前缀和、【模版】二维前缀和、寻找数组的中心下标、除自身以外数组的乘积、和为K的子数组、和可被K整除的子数组、连续数组、矩阵区域和。 #include <iostream>#include <vector>using namespace std;int main() {//1. 读取数据int n = 0, q = 0;ci
阅读更多...
hot100刷题第1-9题，三个专题哈希，双指针，滑动窗口

hot100刷题第1-9题，三个专题哈希，双指针，滑动窗口

求满足条件的子数组，一般是前缀和、滑动窗口，经常结合哈希表； 区间操作元素，一般是前缀和、差分数组 数组有序，更大概率会用到二分搜索 目前已经掌握一些基本套路，重零刷起leetcode hot 100， 套路题按套路来，非套路题适当参考gpt解法。 一、梦开始的地方， 两数之和 class Solution:#注意要返回的是数组下标def twoSum(self, nums: Lis
阅读更多...
牛客小白月赛100部分题解

牛客小白月赛100部分题解

比赛地址：牛客小白月赛100_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ A.ACM中的A题 #include<bits/stdc++.h>using namespace std;#define ll long long#define ull = unsigned long longvoid solve() {ll a,b,c;cin>>a>>b>
阅读更多...
在二叉树中找到两个节点的最近公共祖先（基于Java）

在二叉树中找到两个节点的最近公共祖先（基于Java）

如题  题解 public int lowestCommonAncestor(TreeNode root, int o1, int o2) {//记录遍历到的每个节点的父节点。Map<Integer, Integer> parent = new HashMap<>();Queue<TreeNode> queue = new LinkedList<>();parent.put(roo
阅读更多...
数据结构--二叉树（C语言实现，超详细！！！）

数据结构--二叉树（C语言实现，超详细！！！）

文章目录 二叉树的概念代码实现二叉树的定义创建一棵树并初始化组装二叉树前序遍历中序遍历后序遍历计算树的结点个数求二叉树第K层的结点个数求二叉树高度查找X所在的结点查找指定节点在不在完整代码 二叉树的概念 二叉树（Binary Tree）是数据结构中一种非常重要的树形结构，它的特点是每个节点最多有两个子节点，通常称为左子节点和右子节点。这种结构使得二叉树在数据存储和查找等方面具
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2