# Day 14 二叉树 - 二叉树的层序遍历

## 层序遍历

### 102\. 二叉树的层序遍历

```typescript
function levelOrder(root: TreeNode | null): number[][] {
	if (root === null) {
		return [];
	}
	const result = [];
	const queue = [];
	queue.push(root);
	while (queue.length) {
		const length = queue.length;
		const curResult = [];
		for (let i = 0; i < length; i++) {
			const node = queue.shift();
			curResult.push(node.val);
			node.left && queue.push(node.left);
			node.right && queue.push(node.right);
		}
		result.push(curResult);
	}
	return result;
};
```

### 107\. 二叉树的层序遍历 ii

```typescript
function levelOrderBottom(root: TreeNode | null): number[][] {
	if (root === null) {
		return [];
	}
	const result = [];
	const queue = [root];
	while (queue.length) {
		const length = queue.length;
		const curRes = [];
		for (let i = 0; i < length; i++) {
			const node = queue.shift();
			curRes.push(node.val);
			node.left && queue.push(node.left);
			node.right && queue.push(node.right);
		}
		result.push(curRes);
	}
	return result.reverse();
};
```

### 199\. 二叉树的右视图

> 每一层的最后一个值

```typescript
function rightSideView(root: TreeNode | null): number[] {
	if (root === null) {
		return [];
	}
	const result = [];
	const queue = [root];
	while (queue.length) {
		const length = queue.length;
		for (let i = 0; i < length; i++) {
			const node = queue.shift();
			if (i === length - 1) {
				result.push(node.val);
			}
			node.left && queue.push(node.left);
			node.right && queue.push(node.right);
		}
	}
	return result;
};
```

### 637\. 二叉树的层平均值

```typescript
function averageOfLevels(root: TreeNode | null): number[] {
	if (root === null) {
		return [];
	};
	const result = [];
	const queue = [root];
	while (queue.length) {
		const length = queue.length;
		let curSum = 0;
		for (let i = 0 ; i < length; i++) {
			const node = queue.shift();
			curSum += node.val;
			node.left && queue.push(node.left);
			node.right && queue.push(node.right);
		};
		result.push(curSum / length);
	};
	return result;
};
```

### 429\. N 叉树的层序遍历

```typescript
function levelOrder(root: Node | null): number[][] {
	if (root === null) {
		return [];
	};
	const result = [];
	const queue = [root];
	while (queue.length) {
		const length = queue.length;
		const curRes = [];
		for (let i = 0; i < length; i++) {
			const node = queue.shift();
			curRes.push(node.val);
			node.children && node.children.length > 0 && node.children.forEach((item) => queue.push(item));
		};
		result.push(curRes);
	};
	return result;
};
```

### 515\. 在每个树中找最大值

```typescript
function largestValues(root: TreeNode | null): number[] {
	if (root === null) {
		return [];
	};
	const queue = [root];
	const result = [];
	while (queue.length) {
		const length = queue.length;
		let large = -Infinity;
		for (let i = 0; i < length; i++) {
			const node = queue.shift();
			large = Math.max(large, node.val);
			node.left && queue.push(node.left);
			node.right && queue.push(node.right);
		};
		result.push(large);
	};
	return result;
};
```

### 116\. 填充每个节点的下一个右侧节点指针

```typescript
function connect(root: Node | null): Node | null {
	if (root === null) {
		return root;
	};
	const queue = [root];
	while (queue.length) {
		const length = queue.length;
		for (let i = 0; i < length; i++) {
			const node = queue.shift();
			if (i < length - 1) {
				node.next = queue[0];
			}
			node.left && queue.push(node.left);
			node.right && queue.push(node.right);
		};
	};
	return root;
};
```

### 104\. 二叉树的最大深度

```typescript
function maxDepth(root: TreeNode | null): number {
	if (root === null) {
		return 0;
	}
	let res = 0;
	const queue = [root];
	while (queue.length) {
		const length = queue.length;
		for (let i = 0; i < length; i++) {
			const node = queue.shift();
			node.left && queue.push(node.left);
			node.right && queue.push(node.right);
		};
		res += 1;
	};
	return res;
};
```

### 111\. 二叉树的最小深度

```typescript
function minDepth(root: TreeNode | null): number {
	if (root === null) {
		return 0;
	};
	let res = 0;
	const queue = [root];
	while (queue.length) {
		const length = queue.length;
		res += 1;
		for (let i = 0; i < length; i++) {
			const node = queue.shift();
			if (!node.left && !node.right) {
				return res;
			}
			node.left && queue.push(node.left);
			node.right && queue.push(node.right);
		};
	};
	return res;
};
```

## 226\. 翻转二叉树

### 递归法

```typescript
function invertTree(root: TreeNode | null): TreeNode | null {
	if (root === null) {
		return root;
	}
	const dfs = (node: TreeNode | null) => {
		let temp = node.left;
		node.left = node.right;
		node.right = temp;
		node.left && dfs(node.left);
		node.right && dfs(node.right);
	};
	dfs(root);
	return root;
};
```

### 迭代法

```typescript
function invertTree(root: TreeNode | null): TreeNode | null {
	if (root === null) {
		return root;
	}
	const stack = [root];
	while (stack.length) {
		const node = stack.pop();
		let temp = node.left;
		node.left = node.right;
		node.right = temp;
		node.right && stack.push(node.right);
		node.left && stack.push(node.left);
	};
	return root;
};
```

### 层序遍历

```typescript
function invertTree(root: TreeNode | null): TreeNode | null {
	if (root === null) {
		return root;
	}
	const queue = [root];
	while (queue.length) {
		const length = queue.length;
		for (let i = 0; i < length; i++) {
			const node = queue.shift();
			let temp = node.left;
			node.left = node.right;
			node.right = temp;
			node.left && queue.push(node.left);
			node.right && queue.push(node.right);
		}
	}
	return root;
};
```

## 101\. 对称二叉树

### 递归法

```typescript
function isSymmetric(root: TreeNode | null): boolean {
	const dfs = (left: TreeNode | null, right: TreeNode | null) => {
		if (!left && right) {
			return false;
		}
		if (left && !right) {
			return false;
		}
		if (!left && !right) {
			return true;
		};
		if (left.val !== right.val) {
			return false;
		}
		const outside = dfs(left.left, right.right);
		const inside = dfs(left.right, right.left);
		return outside && inside;
	};
	return dfs(root.left, root.right);
};
```

### 迭代法

```typescript
function isSymmetric(root: TreeNode | null): boolean {
	if (root === null) {
		return true;
	};
	const queue = [];
	queue.push(root.left, root.right);
	while (queue.length) {
		const leftNode = queue.shift();
		const rightNode = queue.shift();
		if (!leftNode && !rightNode) {
			continue;
		};
		if (!leftNode || !rightNode || (leftNode.val !== rightNode.val)) {
			return false;
		};
		queue.push(leftNode.left);
		queue.push(rightNode.right);
		queue.push(leftNode.right);
		queue.push(rightNode.left);
	}
	return true;
};
```