杨乐乐
Never too late

Follow

Never too late

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

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

杨乐乐's photo
杨乐乐
·Jan 28, 2023·

5 min read

Table of contents

层序遍历

102. 二叉树的层序遍历

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

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. 二叉树的右视图

每一层的最后一个值

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. 二叉树的层平均值

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 叉树的层序遍历

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. 在每个树中找最大值

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. 填充每个节点的下一个右侧节点指针

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. 二叉树的最大深度

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. 二叉树的最小深度

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. 翻转二叉树

递归法

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;
};

迭代法

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;
};

层序遍历

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. 对称二叉树

递归法

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);
};

迭代法

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;
};
 
Share this