leetcode 刷题
- 557.反转字符串 III
- 696.计数二进制子串
不同路径问题、最短路径问题、寻求最优解 状态转移方程、最优子结构、边界
- 62.不同路径
- 63.不同路径 II
- 787.K 站中转内最便宜的航班
feliuyg / leetcode Goto Github PK
View Code? Open in Web Editor NEWleetcode刷题
leetcode's Introduction
leetcode's People
Contributors
Watchers
leetcode's Issues
104.二叉树的最大深度
题目：
给定一个二叉树 root ，返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
- 方法一：递归
思路分析：最简单能想到的就是递归，分别看左子树的最大高度和右子树的最大高度，取最大的那个值，然后加上当前一层的1。
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
const maxDepth = function(root: TreeNode | null): number {
if(!root) {
return 0
}
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1
};时间复杂度分析：O(n)， 每个节点只被访问了一次，自顶到底，然后自底到顶的相加。
- 方法二：迭代
思路分析：
使用bfs遍历树，用队列维护树将要访问的当前层节点或下层节点。访问到当前节点就看有没有下层节点（左子树或右子树），就有放入队列中。如何判断是否是当前层，从第一个开始，记录当前层的数量，当前数量访问完，进入下一个层，访问第一个查看数量，再将这些数量访问完，以此类推，直到队列中没有节点。
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function maxDepth(root: TreeNode | null): number {
if(root === null) {
return 0
}
const queue: TreeNode[] = [root]
let h = 0
while(queue.length) {
h++;
let size = queue.length;
while(size--) {
let currentNode = queue.shift();
if(currentNode.left) {
queue.push(currentNode.left)
}
if(currentNode.right) {
queue.push(currentNode.right)
}
}
}
return h;
};时间复杂度分析：O(n)，只会遍历一次，效率会比递归的稍微好一些。
总结：
递归是一种比较简单直观的解法，但缺点是数据量大的情况下，可能会出现栈溢出。
迭代相对来说麻烦一些，需要自己手动维护一个队列，但不太会出现栈溢出的情况，空间占用会少一些。
94.二叉树的中序遍历
题目描述：给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
中序遍历的定义：在二叉树中，中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。根节点属于中间位置访问，所以成为中序遍历，也叫中根遍历。
解题：
1.方法一：递归遍历
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
var inorderTraversal = function(root: TreeNode | null): number[] {
// 递归
const result: number[] = [];
function dps(node: TreeNode | null) {
if(node) {
dps(node.left);
result.push(node.val)
dps(node.right)
}
}
dps(root)
return result;
};时间复杂度：O(n)， 每个节点的值只被访问一次
2.方法二：迭代遍历
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
var inorderTraversal = function(root: TreeNode | null): number[] {
const result: number[] = [];
const stack: TreeNode[] = [];
let current = root;
while(stack.length || current) {
while(current) {
stack.push(current);
current = current.left;
}
const lastNode = stack.pop();
result.push(lastNode.val);
current = lastNode.right
}
return result;
};时间复杂度：O(n)，也是每个节点的值被访问一次
总结：
- 递归实现：
- 优点：简单直观，易于理解
- 缺点：当数的深度非常大时，可能会导致栈溢出，空间复杂度O(h)，h为数的高度
- 迭代实现：
- 优点：空间复杂度较低，最快情况是O(n)，但通常情况树比较平衡时会远低于n
- 缺点：实现相对复杂，需要自己手动维护栈
102.二叉树的层序遍历
题目：给你二叉树的根节点 root ，返回其节点值的 层序遍历 。
层序遍历的定义：逐层地，从左到右访问所有节点。
思路分析：
一层一层地遍历，那么可以用一个队列维护节点，访问到的当前节点的子节点都放在队列后面，先左节点后右节点，这样就能一层一层地从左到右访问。
另外需要记录一层的结束位置，那么在访问到当前层的第一个节点时，记录一下当前层的个数，然后访问到对应个数了表示当前层就访问结束了，接下来就是下一层的节点了。
- 方法一：迭代实现
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
const levelOrder = function(root: TreeNode | null): number[][] {
if(root === null) {
return []
}
const result: number[][] = [];
const queue: TreeNode[] = [root];
while(queue.length) {
let len = queue.length;
const currentFloor: number[] = [];
while(len--) {
const firstNode = queue.shift()
currentFloor.push(firstNode.val)
firstNode.left && queue.push(firstNode.left)
firstNode.right && queue.push(firstNode.right)
}
result.push(currentFloor)
}
return result
};时间复杂度：O(n)，每个节点只访问了一次。
- 方法二：优化版迭代1-链表实现队列
方法一种使用了queue.shift 方法，这个方法的时间复杂度是 O(n) ，如果数据是一个平衡树，那么这个n的数量并不会很大，所以方法一的整体时间复杂度还是 O(n) ，那么如果优化一下这个队列的操作，可以让弹出的方法时间复杂度降为 O(1) ，效率上更高一些。如何实现？可以使用链表或者循环队列。
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function levelOrder(root: TreeNode | null): number[][] {
if(root === null) {
return []
}
const result: number[][] = [];
const queue = new MyQueue();
queue.push(root);
while(queue.length) {
let size = queue.length;
let currentFloor: number[] = [];
while(size--) {
let firstNode = queue.shift()!;
currentFloor.push(firstNode.val);
if(firstNode.left) {
queue.push(firstNode.left)
}
if(firstNode.right) {
queue.push(firstNode.right)
}
}
result.push(currentFloor);
}
return result
};
class MyQueue {
constructor(public head: NodeItem | null = null, public tail: NodeItem | null = null, public length: number = 0) {}
push(val: TreeNode) {
const node = new NodeItem(val);
if(this.head === null) {
this.head = node
}
if(this.tail === null) {
this.tail = node;
} else {
this.tail.next = node;
this.tail = node;
}
this.length++;
}
shift() {
const current = this.head;
const next = this.head.next
this.head.next = null
this.head = next;
this.length--;
return current.val;
}
}
class NodeItem {
constructor(public val: TreeNode, public next: NodeItem | null = null) {}
}- 方法三：优化迭代2-循环队列实现
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function levelOrder(root: TreeNode | null): number[][] {
if(root === null) {
return []
}
const result: number[][] = [];
const queue = new CircularQueue(2000);
queue.push(root);
while(!queue.isEmpty()) {
let size = queue.length;
let currentFloor: number[] = [];
while(size--) {
let firstNode = queue.shift()!;
currentFloor.push(firstNode.val);
if(firstNode.left) {
queue.push(firstNode.left)
}
if(firstNode.right) {
queue.push(firstNode.right)
}
}
result.push(currentFloor);
}
return result
};
class CircularQueue {
capacity: number
items: TreeNode[]
head: number;
tail: number;
constructor(capacity) {
this.capacity = capacity;
this.items = new Array(capacity);
this.head = 0;
this.tail = 0;
}
push(item) {
if ((this.tail + 1) % this.capacity === this.head) {
return false; // 队列已满
}
this.items[this.tail] = item;
this.tail = (this.tail + 1) % this.capacity;
return true;
}
shift() {
if (this.head === this.tail) {
return null; // 队列为空
}
let item = this.items[this.head];
this.head = (this.head + 1) % this.capacity;
return item;
}
isEmpty() {
return this.head === this.tail;
}
get length() {
return this.tail > this.head ? this.tail - this.head : this.capacity - (this.head - this.tail)
}
}- 方法四：递归版本的实现
思路分析：
递归是自底向上的遍历，所以可以借助一个level记录当前的高度，然后遍历到的时候，将其放置在结果集中对应的高度的位置。
这里的前、中、后序位置就无关紧要了，都是可以的。
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function levelOrder(root: TreeNode | null): number[][] {
const result: number[][] = [];
function dfs(node: TreeNode, level: number = 0) {
if(node) {
dfs(node.left, level + 1)
result[level] = (result[level] ?? []).concat(node.val)
dfs(node.right, level + 1)
}
}
dfs(root)
return result;
};时间复杂度：O(n)
总结：
对于层序遍历，使用迭代是一种比较常用的遍历方法，递归的一般使用在前、中、后序遍历中，但层序遍历同样也可以使用递归的方法，只不过需要借助一个额外的变量，记录当前遍历到的层级。这样就可以将值放入对应的位置。
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.