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

对称二叉树

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

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

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

思路: 从根节点开始, 他的左子树和右子树节点比拟, 而后顺次递归上来, 只有有一个不同就返回 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…

相干系列

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