DFS

相关文章：BFS/Topological Sort

Tree实现DFS

递归实现

public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ans = new LinkedList<>();
        // recursion solution
        if (root != null) {
            DFS(ans, root);
        }
}

private void DFS(List<Integer> ans, TreeNode cur) {
        if (cur.left != null) {
            DFS(ans, cur.left);
        }
        ans.add(cur.val);
        if (cur.right != null) {
            DFS(ans, cur.right);
        }
}

N = numbers of nodes, H = tree height
时间复杂度：O(N), go to every node
空间复杂度：O(H), if balanced O(logN), if not balanced O(N)

Stack实现

public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ans = new LinkedList<>();
        // iterative solution
        TreeNode cur = root;
        Stack<TreeNode> stack = new Stack<>();
        while(cur!=null || !stack.empty()){
            while(cur!=null){
                stack.add(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            ans.add(cur.val);
            cur = cur.right;
        }
        return ans;
}

N = numbers of nodes, H = tree height
时间复杂度：O(N), go to every node
空间复杂度：O(H), if balanced O(logN), if not balanced O(N)

Morris Traversal

Morris Traversal可以使二叉树的DFS空间复杂度为O(1)
核心概念是让当前节点的左子树的最右叶子结点的右孩子指向当前节点，于是可以达到不用迭代/压栈也可以在遍历完左子树后通过cycle回到当前节点

具体操作：
1、cur.left 为 null，保存 cur 的值，更新 cur = cur.right
2、cur.left 不为 null，找到 cur.left 这颗子树最右边的节点记做 last
2.1 last.right 为 null，那么将 last.right = cur，更新 cur = cur.left
2.2 last.right 不为 null，说明之前已经访问过，第二次来到这里，表明当前子树遍历完成，保存 cur 的值，更新 cur = cur.right

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    TreeNode cur = root;
    while (cur != null) {
        //情况 1
        if (cur.left == null) {
            ans.add(cur.val);
            cur = cur.right;
        } else {
            //找左子树最右边的节点
            TreeNode pre = cur.left;
            while (pre.right != null && pre.right != cur) {
                pre = pre.right;
            }
            //情况 2.1
            if (pre.right == null) {
                pre.right = cur;
                cur = cur.left;
            }
            //情况 2.2
            if (pre.right == cur) {
                pre.right = null; //这里可以恢复为 null
                ans.add(cur.val);
                cur = cur.right;
            }
        }
    }
    return ans;
}
N = numbers of nodes, H = tree height
**时间复杂度：O(N), go to every node**    
**空间复杂度：O(1)**

Matrix实现DFS

向满足条件的前后左右遍历，存储值并设置为已读

    public int numIslands(char[][] grid) {
        if (grid.length==0) {
            return 0;
        } else {
            int count = 0;
            for (int i=0; i<grid.length; i++) {
                for (int j=0; j<grid[0].length; j++) {
                    if (grid[i][j] == '1') {
                        dfs(grid, i, j);
                        count++;
                    }
                }
            }
            return count;
        }      
    }
    
    private void dfs(char[][] grid, int row, int column) {
        if (0<=row && row<grid.length && 0<=column && column<grid[0].length && grid[row][column] == '1') {
            grid[row][column] = '#';
            dfs(grid, row-1, column);
            dfs(grid, row+1, column);
            dfs(grid, row, column-1);
            dfs(grid, row, column+1);
        }
    }

N = numbers of rows of the matrix, M = numbers of columns of the matrix
时间复杂度：O(NM)
空间复杂度：O(NM) for recursion

Graph实现DFS

N = numbers of graph nodes, M = numbers of edges
时间复杂度：O(N+M)
空间复杂度：at worst O(N+M) for one single path

相关练习

Tree

Leetcode CN 94 - 二叉树的中序遍历
Leetcode CN 94 - 二叉树的最大深度
Leetcode CN 230 - 二叉搜索树中第K小的元素
Leetcode CN 337 - 打家劫舍III

Matrix

Leetcode CN 547 - 朋友圈
Leetcode CN 417 - 太平洋大西洋水流问题
Leetcode CN 200 - 岛屿数量

Graph

Leetcode CN 207 - 课程表

参考文献

Morris Traversal详解