二叉树部分操作
字数
1566 字
阅读时间
8 分钟
因为二叉树的数据结构特性天然支持递归，所以二叉树的一般操作都存在迭代和递归两种实现方式。
翻转二叉树
思路：本质上是遍历二叉树，在“读入”节点时修改其左右子节点的指向，从而实现翻转。
迭代法
javascript
/**
* 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)
* }
*/
/**
* @param {TreeNode} root
* @return {TreeNode}
*/
var invertTree = function(root) {
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;
// 将子节点入栈，以便后续处理
if (node.right) {
stack.push(node.right);
}
if (node.left) {
stack.push(node.left);
}
}
return root;
};递归法
javascript
/**
* 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)
* }
*/
/**
* @param {TreeNode} root
* @return {TreeNode}
*/
var invertTree = function(root) {
if (root === null) {
return root;
}
// 递归翻转左右子树
invertTree(root.left);
invertTree(root.right);
// 交换当前节点的左右子节点
let temp = root.left;
root.left = root.right;
root.right = temp;
return root;
};对称二叉树
思路：对称二叉树可以看作镜像二叉树。判断镜像的巧妙方式是比较左右子树是否对称，即比较 左子树的左节点 与 右子树的右节点，以及 左子树的右节点 与 右子树的左节点。
迭代法
javascript
/**
* 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)
* }
*/
/**
* @param {TreeNode} root
* @return {boolean}
*/
var isSymmetric = function(root) {
if (root === null) return true;
let queue = [];
queue.push(root.left);
queue.push(root.right);
while (queue.length) {
let leftNode = queue.shift();
let rightNode = queue.shift();
// 左右节点都为空，则对称，继续检查队列中的其他节点
if (leftNode === null && rightNode === null) continue;
// 左右节点有一个为空，或者值不相等，则不对称
if (leftNode === null || rightNode === null || leftNode.val !== rightNode.val) return false;
// 注意入队顺序：左子树的左孩子与右子树的右孩子，左子树的右孩子与右子树的左孩子
queue.push(leftNode.left);
queue.push(rightNode.right);
queue.push(leftNode.right);
queue.push(rightNode.left);
}
return true;
};递归法
javascript
/**
* 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)
* }
*/
/**
* @param {TreeNode} root
* @return {boolean}
*/
var isSymmetric = function(root) {
if (root === null) return true; // 空树是对称的
const compareTwo = function(left, right) {
// 左右节点都为空，则对称
if (left === null && right === null) return true;
// 左右节点有一个为空，或者值不相等，则不对称
if (left === null || right === null || left.val !== right.val) return false;
// 递归比较外侧节点和内侧节点
let outSide = compareTwo(left.left, right.right);
let inSide = compareTwo(left.right, right.left);
return outSide && inSide;
};
return compareTwo(root.left, root.right);
};二叉树的最大深度
思路：可以使用层序遍历（广度优先遍历）来计算二叉树的最大深度。每遍历一层，深度加一。
javascript
/**
* 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)
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var maxDepth = function(root) {
let depth = 0;
if (root === null) {
return depth;
}
const queue = [root];
while (queue.length) {
let size = queue.length; // 当前层的节点数量
depth++; // 深度加一
for (let i = 0; i < size; i++) { // 遍历当前层的所有节点
let node = queue.shift();
if (node.left) {
queue.push(node.left);
}
if (node.right) {
queue.push(node.right);
}
}
}
return depth;
};二叉树的最小深度
思路：与最大深度类似，但需要注意的是，当一个节点只有一个子节点时，最小深度不是 1，而是 1 加上其存在的子树的最小深度。只有当左右子节点都为空时，才算到达叶子节点。
javascript
/**
* 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)
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var minDepth = function(root) {
const getMinDepth = function(node) {
if (node === null) return 0;
let leftDepth = getMinDepth(node.left);
let rightDepth = getMinDepth(node.right);
// 如果左子树为空，右子树不为空，则最小深度为 1 + 右子树的最小深度
if (node.left === null && node.right !== null) {
return 1 + rightDepth;
}
// 如果右子树为空，左子树不为空，则最小深度为 1 + 左子树的最小深度
if (node.left !== null && node.right === null) {
return 1 + leftDepth;
}
// 左右子树都不为空，则最小深度为 1 + 左右子树中较小的深度
const depth = 1 + Math.min(leftDepth, rightDepth);
return depth;
};
return getMinDepth(root);
};完全二叉树的节点个数
222. 完全二叉树的节点个数 - 力扣（LeetCode）
思路：完全二叉树有两种情况：
- 满二叉树：可以直接用
2^树深度 - 1来计算（根节点深度为 1）。 - 最后一层叶子节点未满：分别递归计算左子树和右子树的节点个数。在递归过程中，如果发现某个子树是满二叉树，则按情况 1 计算。
javascript
/**
* 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)
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var countNodes = function(root) {
if (root === null) return 0;
let left = root.left;
let right = root.right;
let leftHeight = 0;
let rightHeight = 0;
// 计算左子树的高度
while (left) {
leftHeight++;
left = left.left;
}
// 计算右子树的高度
while (right) {
rightHeight++;
right = right.right;
}
// 如果左右子树高度相等，说明以当前节点为根的树是满二叉树
if (leftHeight === rightHeight) {
return (2 << leftHeight) - 1; // 2^height - 1
}
// 否则，递归计算左右子树的节点数，并加上根节点本身
return countNodes(root.left) + countNodes(root.right) + 1;
};
<NolebaseGitContributors />
<NolebaseGitChangelog />