DFS模式-DEV365 开发者社区

此博客旨在列出涉及DFS模式的一些leetcode问题。

首先。让我们看看DFS模式是什么，DFS具有3种类型：预订，inorder，posterder；它们之间的区别是遍历顺序。

预订：中间 - >左---->右
inorder：左---->中间 - >右
邮递：左--->右--->中间

例如，有一个二进制树：

预订遍历为5 4 1 2 6 7 8
内部遍历为1 4 2 5 7 6 8
postordertraversal是1 2 4 7 8 6 5

ð¢dfs-预订递归模式：

const preorderTraversal = (root) => {
  let visted = [];

  const helper = (node) => {
    if (!node) return;

    visted.push(node.val); // middle
    helper(node.left); // left
    helper(node.right); // right
  };

  helper(root);
  return visted;
};

ð¢dfs-秩序递归模式：

const inorderTraversal = (root) => {
  let visted = [];

  const helper = (node) => {
    if (!node) return;

    helper(node.left); // left
    visted.push(node.val); // middle
    helper(node.right); // right
  };

  helper(root);
  return visted;
};

ð¢dfs-后订单递归模式：

const postorderTraversal = (root) => {
  let visted = [];

  const helper = (node) => {
    if (!node) return;

    helper(node.left); // left
    helper(node.right); // right
    visted.push(node.val); // middle
  };

  helper(root);
  return visted;
};

我们还可以以叠加方式以迭代方式实现DFS：

ðâdfs-预订迭代：

/* out of stack: middle->left->right, 
    enter stack: right -> left */

const preorderTraversal = (root) => {const preorderTraversal = (root) =>     
    let visited = [];
    let stack = [root];

    while(stack.length){
        let node = stack.pop();

        visited.push(node.val); // middle
        if(node.right)stack.push(node.right);  // right
        if(node.left) stack.push(node.left) // left
    }


    return visited;
};

ðâdfs-订购迭代：

/* out of stack: left->middle->right, 
    enter stack: left->right */

const inorderTraversal = (root) => {
    const visited = []
    const stack = [];
    let curr = root; //用指针用来访问节点

    while(stack.length || curr) {
        //一路向左
        if(curr) { 
            stack.push(curr);
            curr = curr.left;
        } else {
            curr = stack.pop(); // --> 弹出 中
            visited.push(curr.val); 
            curr = curr.right; // 右
        }
    };

    return visited;
};

ðâdfs-订单后迭代：

/* out of stack: middle->right->left, 
    enter stack: left->right */
const postorderTraversal = (root) => {
    let visited = [];
    let stack = [root];

    while(stack.length){
        let node = stack.pop();

        if(node) visited.push(node.val);//middle
        if(node.left) stack.push(node.left);//left
        if(node.right) stack.push(node.right);//right
    }

    // middle->right->left reverse to left->right->middle
    return visited.reverse();
};

然后，基于上述DFS模式，我们可以在leetcode中删除一些问题。示例：
144. Binary Tree Preorder Traversal
145. Binary Tree Postorder Traversal
94. Binary Tree Inorder Traversal
226. Invert Binary Tree
100. Same Tree
572. Subtree of Another Tree
98. Validate Binary Search Tree
236. Lowest Common Ancestor of a Binary Tree
104. Maximum Depth of Binary Tree