关于前端:二叉树二-补充

对称二叉树

创立一个函数，用来判断一颗二叉树是不是对称的

如图, 这就是对称的二叉树

留神下图, 不是对称二叉树

思路: 从根节点开始, 他的左子树和右子树节点比拟, 而后顺次递归上来, 只有有一个不同就返回 false

const isSymmetric = function (root) {    if (root === null) return true    return isEqual(root.left, root.right)};const isEqual = function (left, right) {    if (left === null) {        return right === null    }    if (right === null) {        // 到这里 left 必定不为空, 所以 left !== right         return false    }    if (left.val !== right.val) {        return false;    }    // 到这一步, 阐明 left,right 不为空且相等    // 持续比拟    return isEqual(left.left, right.right)        && isEqual(left.right, right.left)}

雷同的树

思路:

• 如果两个二叉树都为空，则它们雷同返回 true。
• 如果两个二叉树中有一个为空，则它们不同返回 false。
• 如果两个二叉树都不为空，首先判断根节点是否雷同，不同则返回 false。
• 如果两个二叉树的根节点雷同，则别离递归判断其左右子树是否雷同。

const isSameTree = function (p, q) {    if (p === null && q === null) {        return true;    }    if (p === null || q === null) {        return false;    }    if (p.val !== q.val) {        return false;    }    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);};

深度优先搜寻

说起来和遍历和差不多, 差距在于搜寻到指标时会返回

const dfs = (value) => {    const stack = [root]    while (stack.length) {        const current = stack.pop()        console.log(current)        if (current.node === value) {            return current        }        current.right && stack.push(current.right)        current.left && stack.push(current.left)    }}

广度优先搜寻

const bfs = (value) => {    const queue = [root]    while (queue.length) {        const current = queue.shift()        console.log(current)        if (current.node === value) {            return current        }        current.left && queue.push(current.left)        current.right && queue.push(current.right)    }}

这里和深度比拟下, 能够看出最大的区别就是 栈和队列

翻转二叉树

翻墙二叉树的要求: 它的所有左右子树要替换地位。

const invertTree = function (root) {    if (root == null) return null // 递归终止条件    // 替换左右两节点    const temp = root.left    root.left = root.right    root.right = temp        // 顺次递归子节点    invertTree(root.left)    invertTree(root.right)        return root}

计划二:

const invertTree = function (root) {    if (root == null) return null // 递归终止条件    const stack = [root]        while (stack.length){        const current = stack.pop()        const temp = current.left        current.left = current.right        current.right = temp                current.right && stack.push(current.right)        current.left && stack.push(current.left)    }        return root}

结语

这一部分是二叉树的其余计划和状况

仓库地址: https://github.com/Grewer/notes

参考:

• https://zh.wikipedia.org/wiki...
• https://zh.wikipedia.org/wiki...

相干系列

• 二叉树(一): 遍历
• 二叉树(二): 补充
• 二叉树(三): 二叉查找树