leetcode 刷题
- 557.反转字符串 III
- 696.计数二进制子串
不同路径问题、最短路径问题、寻求最优解 状态转移方程、最优子结构、边界
- 62.不同路径
- 63.不同路径 II
- 787.K 站中转内最便宜的航班
leetcode刷题
leetcode 刷题
不同路径问题、最短路径问题、寻求最优解 状态转移方程、最优子结构、边界
题目:
给定一个二叉树 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),只会遍历一次,效率会比递归的稍微好一些。
总结:
递归是一种比较简单直观的解法,但缺点是数据量大的情况下,可能会出现栈溢出。
迭代相对来说麻烦一些,需要自己手动维护一个队列,但不太会出现栈溢出的情况,空间占用会少一些。
题目描述:给定一个二叉树的根节点 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),也是每个节点的值被访问一次
总结:
题目:给你二叉树的根节点 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)
,每个节点只访问了一次。
方法一种使用了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) {}
}
/**
* 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)
总结:
对于层序遍历,使用迭代是一种比较常用的遍历方法,递归的一般使用在前、中、后序遍历中,但层序遍历同样也可以使用递归的方法,只不过需要借助一个额外的变量,记录当前遍历到的层级。这样就可以将值放入对应的位置。
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.