树相关算法总结

我会带着你远行 2022-11-14 10:25 83阅读 0赞

## 1二叉树的中序遍历 ##

中序遍历：先打印当前节点的左子树，再打印当前节点，最后打印当前节点的右子树

**const inorderTraversal = function(root) { 
        const result = [];
        function pushRoot(root) { 
            if (root !== null) { 
                if (root.left !== null) { 
                    pushRoot(root.left);
                }
                result.push(root.val);
                if (root.right !== null) {  
                    pushRoot(root.right);
                }
            }
        }
        pushRoot(root);
        return result;
    };**

时间复杂度: O(n)  
空间复杂度: O(n)

## 2二叉树的前序遍历 ##

前序遍历：先打印当前节点，再打印当前节点的左子树，最后打印当前节点的右子树

时间复杂度: O(n)  
空间复杂度: O(n)

## 3 二叉树的后序遍历 ##

后序遍历：先打印当前节点的左子树，再打印当前节点的右子树，最后打印当前节点

时间复杂度: O(n)  
空间复杂度: O(n)

## 4相同的树 ##

**深度优先搜索 DFS**  
如果两个二叉树都为空，则它们相同返回 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);
    };

时间复杂度: O(min(m, n))  
空间复杂度: O(min(m, n))

## 5 对称二叉树 ##

**递归**  
先明确，所谓“对称”，也就是两个树的根节点相同且  
第一个树的左子树与第二个树的右子树镜像对称。  
第一个树的右子树与第二个树的左子树镜像对称。

const isSymmetric = function(root) { 
        if (root === null) return true
        return isEqual(root.left, root.right) // 比较左右子树是否对称
    };
    
    const isEqual = function(left, right) { 
        // 递归终止条件
        if (left === null && right === null) return true // 对称
        if (left === null || right === null) return false // 不对称
        // 比较左右子树的 root 值以及左右子树是否对称
        return left.val === right.val
            && isEqual(left.left, right.right)
            && isEqual(left.right, right.left)
    }

时间复杂度: O(n)  
空间复杂度: O(n)

## 6 二叉树的层序遍历 ##

**DFS 深度优先遍历**  
按照树的深度将每层对应的节点添加到对应层的数组中即可。

const levelOrder = function(root) { 
        if (!root) return []
        const res = []
        dfs(root, 0, res)
        return res
    };
    
    const dfs = function(root, depth, res) { 
        if (!root) return // 递归终止条件
        if (!res[depth]) res[depth] = []
        res[depth].push(root.val) // 存入每层的节点值
        dfs(root.left, depth + 1, res) // drill down
        dfs(root.right, depth + 1, res)
    }

**BFS 广度优先遍历**  
根据层次返回其对应的结果集合。

边界处理，初始化队列 queue 和存放结果的数组 res。  
外层循环遍历层级结构，内层循环遍历每一层的子节点。  
遍历时需要记录当前层的遍历次数 len 以及当前层的节点数组 arr。  
取得 node 依次出队，并依次存入当前层的节点数组中。  
若存在左右子节点，则依次入队，并更新 len。  
遍历完后返回结果 res。

const levelOrder = function(root) { 
        if (!root) return []
        const queue = [root]
        const res = []
        while (queue.length > 0) { 
          const arr = []
          let len = queue.length
          while (len) { 
            let node = queue.shift()
            arr.push(node.val)
            if (node.left) queue.push(node.left)
            if (node.right) queue.push(node.right)
            len--
          }
          res.push(arr)
        }
        return res
    };

时间复杂度: O(n)  
空间复杂度: O(n)

## 7二叉树的最大深度 ##

**DFS 深度优先搜索**  
树的深度 = 左右子树的最大深度 + 1

const maxDepth = function(root) { 
        if (!root) {  // 递归终止条件
            return 0
        } else { 
            const left = maxDepth(root.left)
            const right = maxDepth(root.right)
            return Math.max(left, right) + 1
        }
    };

时间复杂度: O(n)  
最坏空间复杂度: O(height), height 表示二叉树的高度  
**BFS 广度优先搜索**  
层序遍历时记录树的深度

const maxDepth = function(root) { 
        let depth = 0
        if (root === null) { 
            return depth
        }
        const queue = [root]
        while (queue.length) { 
            let len = queue.length
            while (len--) { 
                const cur = queue.shift()
                cur.left && queue.push(cur.left)
                cur.right && queue.push(cur.right)
            }
            depth++
        }
        return depth
    };

时间复杂度: O(n)  
空间复杂度: O(n)  
**BFS**  
层序遍历遍历二叉树，当根结点出列时，翻转它的左右子树。然后将其左右子节点入列，以便下一层时翻转。

const invertTree = (root) => { 
      if (root == null) return null;
      const queue = [root];
      while (queue.length) { 
        const cur = queue.shift();
        [cur.left, cur.right] = [cur.right, cur.left];
        if (cur.left) queue.push(cur.left);
        if (cur.right) queue.push(cur.right);
      }
      return root;
    }