@Yano 2015-12-30T03:27:46.000000Z 字数 18923 阅读 8400

# LeetCode之Depth-first Search题目汇总

LeetCode

LeetCode 题目汇总

# Balanced Binary Tree

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

return  Math.abs(height(root.left)  - height(root.right))  <=  1  && isBalanced(root.left)  && isBalanced(root.right);
    public boolean isBalanced(TreeNode root) {        if (root == null) {            return true;        }        return Math.abs(height(root.left) - height(root.right)) <= 1                && isBalanced(root.left) && isBalanced(root.right);    }    int height(TreeNode node) {        if (node == null) {            return 0;        }        return Math.max(height(node.left), height(node.right)) + 1;    }

# Binary Tree Paths

Given a binary tree, return all root-to-leaf paths.

For example, given the following binary tree:

   1 /   \2     3 \  5

All root-to-leaf paths are:

["1->2->5", "1->3"]

Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

    List<String> rt = new ArrayList<String>();    List<Integer> path = new ArrayList<Integer>();    public List<String> binaryTreePaths(TreeNode root) {        findPath(root);        return rt;    }    void findPath(TreeNode root) {        if (root == null) {            return;        }        path.add(root.val);        // 是一条路径，将path添加到rt中        if (root.left == null && root.right == null) {            StringBuffer sb = new StringBuffer();            sb.append(path.get(0));            for (int i = 1; i < path.size(); i++) {                sb.append("->" + path.get(i));            }            rt.add(sb.toString());        }        findPath(root.left);        findPath(root.right);        path.remove(path.size() - 1);    }

# Binary Tree Right Side View

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

For example:
Given the following binary tree,

   1            <--- /   \2     3         <--- \     \  5     4       <---

You should return [1, 3, 4].

Credits:
Special thanks to @amrsaqr for adding this problem and creating all test cases.

1. 递归求解

       1  <---      / \     2   3  <---     \    \      5    4  <---       \        6       <---

list1是[1, 3, 4], list2是[1, 2, 5, 6]。list2比list1长，长出的部分是6，也在结果之中。

    public List<Integer> rightSideView(TreeNode root) {        List<Integer> rt = new ArrayList<Integer>();        if (root == null) {            return rt;        }        rt.add(root.val);        List<Integer> left = rightSideView(root.left);        List<Integer> right = rightSideView(root.right);        rt.addAll(right);        if (left.size() > right.size()) {            rt.addAll(left.subList(right.size(), left.size()));        }        return rt;    }

2. 插入特殊结点

    public List<Integer> rightSideView2(TreeNode root) {        List<Integer> rt = new ArrayList<Integer>();        if (root == null) {            return rt;        }        final TreeNode END = new TreeNode(0);        Deque<TreeNode> deque = new LinkedList<TreeNode>();        deque.add(root);        deque.add(END);        while (!deque.isEmpty()) {            TreeNode p = deque.pop();            if (p == END) {                if (!deque.isEmpty()) {                    deque.add(END);                }            } else {                // 如果deque的下一个是END，则p是层序的最后一个，加入结果rt                if (deque.peek() == END) {                    rt.add(p.val);                }                if (p.left != null) {                    deque.add(p.left);                }                if (p.right != null) {                    deque.add(p.right);                }            }        }        return rt;    }

3. 计数法

toBePrinted：当前待打印结点的数量
nextLevel：下一层的结点数量

    public List<Integer> rightSideView3(TreeNode root) {        List<Integer> rt = new ArrayList<Integer>();        if (root == null) {            return rt;        }        Deque<TreeNode> deque = new LinkedList<TreeNode>();        deque.add(root);        int toBePrinted = 1;        int nextLevel = 0;        List<Integer> level = new LinkedList<Integer>();        while (!deque.isEmpty()) {            TreeNode p = deque.poll();            level.add(p.val);            toBePrinted--;            if (p.left != null) {                deque.addLast(p.left);                nextLevel++;            }            if (p.right != null) {                deque.addLast(p.right);                nextLevel++;            }            if (toBePrinted == 0) {                toBePrinted = nextLevel;                nextLevel = 0;                rt.add(p.val);                level.clear();            }        }        return rt;    }

# Construct Binary Tree from Inorder and Postorder Traversal

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

    int p;    int[] postorder;    int[] inorder;    public TreeNode buildTree(int[] inorder, int[] postorder) {        this.p = postorder.length - 1;        this.inorder = inorder;        this.postorder = postorder;        return buildTree(0, postorder.length);    }    TreeNode buildTree(int start, int end) {        if (start >= end) {            return null;        }        TreeNode root = new TreeNode(postorder[p]);        int i;        for (i = start; i < end && postorder[p] != inorder[i]; i++)            ;        p--;        root.right = buildTree(i + 1, end);        root.left = buildTree(start, i);        return root;    }

# Construct Binary Tree from Preorder and Inorder Traversal

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

    int p = 0;    int[] preorder;    int[] inorder;    public TreeNode buildTree(int[] preorder, int[] inorder) {        this.preorder = preorder;        this.inorder = inorder;        return buildTree(0, preorder.length);    }    TreeNode buildTree(int start, int end) {        if (start >= end) {            return null;        }        TreeNode root = new TreeNode(preorder[p]);        int i;        for (i = start; i < end && preorder[p] != inorder[i]; i++)            ;        p++;        root.left = buildTree(start, i);        root.right = buildTree(i + 1, end);        return root;    }

# Convert Sorted Array to Binary Search Tree

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

    int[] nums;    public TreeNode sortedArrayToBST(int[] nums) {        this.nums = nums;        return buildBST(0, nums.length);    }    TreeNode buildBST(int start, int end) {        if (start >= end) {            return null;        }        int mid = (start + end) / 2;        TreeNode root = new TreeNode(nums[mid]);        root.left = buildBST(start, mid);        root.right = buildBST(mid + 1, end);        return root;    }    public TreeNode sortedArrayToBST2(int[] nums) {        if (nums.length == 0) {            return null;        }        if (nums.length == 1) {            return new TreeNode(nums[0]);        }        int mid = nums.length / 2;        TreeNode root = new TreeNode(nums[mid]);        root.left = sortedArrayToBST2(Arrays.copyOfRange(nums, 0, mid));        root.right = sortedArrayToBST2(Arrays.copyOfRange(nums, mid + 1,                nums.length));        return root;    }

# Convert Sorted List to Binary Search Tree

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

    ListNode cutAtMid(ListNode head) {        if (head == null) {            return null;        }        ListNode fast = head;        ListNode slow = head;        ListNode pslow = head;        while (fast != null && fast.next != null) {            pslow = slow;            slow = slow.next;            fast = fast.next.next;        }        pslow.next = null;        return slow;    }    public TreeNode sortedListToBST(ListNode head) {        if (head == null) {            return null;        }        if (head.next == null) {            return new TreeNode(head.val);        }        ListNode mid = cutAtMid(head);        TreeNode root = new TreeNode(mid.val);        root.left = sortedListToBST(head);        root.right = sortedListToBST(mid.next);        return root;    }

# Course Schedule

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

For example:

2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

2, [[1,0],[0,1]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

Note:
The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.

BFS:

    // BFS    public static boolean canFinish(int numCourses, int[][] prerequisites) {        // 参数检查        if (prerequisites == null) {            return false;        }        int len = prerequisites.length;        if (numCourses <= 0 || len == 0) {            return true;        }        // 记录每个course的prerequisites的数量        int[] pCounter = new int[numCourses];        for (int i = 0; i < len; i++) {            pCounter[prerequisites[i][0]]++;        }        // 用队列记录可以直接访问的course        LinkedList<Integer> queue = new LinkedList<Integer>();        for (int i = 0; i < numCourses; i++) {            if (pCounter[i] == 0) {                queue.add(i);            }        }        // 取出队列的course，判断        int numNoPre = queue.size();        while (!queue.isEmpty()) {            int top = queue.remove();            for (int i = 0; i < len; i++) {                // 该course是某个course的prerequisites                if (prerequisites[i][1] == top) {                    pCounter[prerequisites[i][0]]--;                    if (pCounter[prerequisites[i][0]] == 0) {                        numNoPre++;                        queue.add(prerequisites[i][0]);                    }                }            }        }        return numNoPre == numCourses;    }

DFS:

    // DFS    public static boolean canFinish2(int numCourses, int[][] prerequisites) {        // 参数检查        if (prerequisites == null) {            return false;        }        int len = prerequisites.length;        if (numCourses <= 0 || len == 0) {            return true;        }        int[] visit = new int[numCourses];        // key：course；value：以该course为prerequisites的course        HashMap<Integer, ArrayList<Integer>> map = new HashMap<Integer, ArrayList<Integer>>();        // 初始化map        for (int[] p : prerequisites) {            if (map.containsKey(p[1])) {                map.get(p[1]).add(p[0]);            } else {                ArrayList<Integer> l = new ArrayList<Integer>();                l.add(p[0]);                map.put(p[1], l);            }        }        // dfs        for (int i = 0; i < numCourses; i++) {            if (!canFinishDFS(map, visit, i)) {                return false;            }        }        return true;    }    private static boolean canFinishDFS(            HashMap<Integer, ArrayList<Integer>> map, int[] visit, int i) {        if (visit[i] == -1) {            return false;        }        if (visit[i] == 1) {            return true;        }        visit[i] = -1;        // course i是某些course的prerequisites        if (map.containsKey(i)) {            for (int j : map.get(i)) {                if (!canFinishDFS(map, visit, j)) {                    return false;                }            }        }        visit[i] = 1;        return true;    }

# Course Schedule II

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.

There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.

For example:

2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1]

4, [[1,0],[2,0],[3,1],[3,2]]

There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is[0,2,1,3].

Note:
The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.

Hints:

1. This problem is equivalent to finding the topological order in a directed graph. If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses.
2. Topological Sort via DFS - A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort.
3. Topological sort could also be done via BFS.

    public int[] findOrder(int numCourses, int[][] prerequisites) {        // 参数检查        if (prerequisites == null) {            throw new IllegalArgumentException();        }        int len = prerequisites.length;        if (len == 0) {            int[] seq = new int[numCourses];            for (int i = 0; i < seq.length; i++) {                seq[i] = i;            }            return seq;        }        int[] seq = new int[numCourses];        int c = 0;        // 记录每个course的prerequisites的数量        int[] pCounter = new int[numCourses];        for (int i = 0; i < len; i++) {            pCounter[prerequisites[i][0]]++;        }        // 用队列记录可以直接访问的course        LinkedList<Integer> queue = new LinkedList<Integer>();        for (int i = 0; i < numCourses; i++) {            if (pCounter[i] == 0) {                queue.add(i);            }        }        // 取出队列的course，判断        int numNoPre = queue.size();        while (!queue.isEmpty()) {            int top = queue.remove();            // 保存结果 +_+            seq[c++] = top;            for (int i = 0; i < len; i++) {                // 该course是某个course的prerequisites                if (prerequisites[i][1] == top) {                    pCounter[prerequisites[i][0]]--;                    if (pCounter[prerequisites[i][0]] == 0) {                        numNoPre++;                        queue.add(prerequisites[i][0]);                    }                }            }        }        if (numNoPre != numCourses) {            return new int[] {};        }        return seq;    }

# Flatten Binary Tree to Linked List

Given a binary tree, flatten it to a linked list in-place.

For example,
Given

         1        / \       2   5      / \   \     3   4   6

The flattened tree should look like:

   1    \     2      \       3        \         4          \           5            \             6

click to show hints.

    TreeNode prev;    void preorder(TreeNode root) {        if (root == null)            return;        TreeNode left = root.left;        TreeNode right = root.right;        // root        if (prev != null) {            prev.right = root;            prev.left = null;        }        prev = root;        preorder(left);        preorder(right);    }    public void flatten(TreeNode root) {        prev = null;        preorder(root);    }

# Maximum Depth of Binary Tree

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

    public int maxDepth(TreeNode root) {        if (root == null) {            return 0;        }        int nLeft = maxDepth(root.left);        int nRight = maxDepth(root.right);        return nLeft > nRight ? (nLeft + 1) : (nRight + 1);    }

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

Minimum Depth的定义如下：

    public int minDepth(TreeNode root) {        if (root == null) {            return 0;        }        if (root.left == null && root.right == null) {            return 1;        } else if (root.left != null && root.right == null) {            return minDepth(root.left) + 1;        } else if (root.left == null && root.right != null) {            return minDepth(root.right) + 1;        }        return Math.min(minDepth(root.left), minDepth(root.right)) + 1;    }

# Number of Islands

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

11110110101100000000

Example 2:

11000110000010000011

Credits:
Special thanks to @mithmatt for adding this problem and creating all test cases.

dfs，遍历过的grid如果是’1’，变成其它字符。

    int mx, my;    public int numIslands(char[][] grid) {        if (grid == null || grid.length == 0 || grid[0].length == 0) {            return 0;        }        mx = grid.length;        my = grid[0].length;        int rt = 0;        for (int x = 0; x < mx; x++) {            for (int y = 0; y < my; y++) {                if (grid[x][y] != '1') {                    continue;                }                rt++;                dfs(grid, x, y);            }        }        return rt;    }    void dfs(char[][] grid, int x, int y) {        if (x < 0 || x >= mx || y < 0 || y >= my) {            return;        }        if (grid[x][y] == '1') {            grid[x][y] = '2';            dfs(grid, x + 1, y);            dfs(grid, x - 1, y);            dfs(grid, x, y + 1);            dfs(grid, x, y - 1);        }    }

# Path Sum

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example:
Given the below binary tree and sum = 22,

              5             / \            4   8           /   / \          11  13  4         /  \      \        7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

    boolean hasPath;    public boolean hasPathSum(TreeNode root, int sum) {        if (root == null) {            return false;        }        hasPath = false;        help(root, 0, sum);        return hasPath;    }    void help(TreeNode node, int cur, int sum) {        cur += node.val;        boolean isLeaf = (node.left == null) && (node.right == null);        if (cur == sum && isLeaf) {            hasPath = true;        }        if (node.left != null) {            help(node.left, cur, sum);        }        if (node.right != null) {            help(node.right, cur, sum);        }        cur -= node.val;    }

    public boolean hasPathSum2(TreeNode root, int sum) {        if (root == null) {            return false;        }        if (root.left == null && root.right == null) {            return root.val == sum;        }        return (root.left != null && hasPathSum2(root.left, sum - root.val))                || (root.right != null && hasPathSum2(root.right, sum                        - root.val));    }

# Path Sum II

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

For example:
Given the below binary tree and sum = 22,

              5             / \            4   8           /   / \          11  13  4         /  \    / \        7    2  5   1

return

[   [5,4,11,2],   [5,8,4,5]]

    List<List<Integer>> result;    List<Integer> path;    int sum;    public List<List<Integer>> pathSum(TreeNode root, int sum) {        result = new ArrayList<List<Integer>>();        path = new ArrayList<Integer>();        this.sum = sum;        if (root == null) {            return result;        }        help(root, 0);        return result;    }    void help(TreeNode node, int cur) {        cur += node.val;        path.add(node.val);        boolean isLeaf = (node.left == null) && (node.right == null);        if (cur == sum && isLeaf) {            result.add(new ArrayList<Integer>(path));        }        if (node.left != null) {            help(node.left, cur);        }        if (node.right != null) {            help(node.right, cur);        }        cur -= node.val;        path.remove(path.size() - 1);    }

# Populating Next Right Pointers in Each Node

Given a binary tree

struct TreeLinkNode {
}


Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Note:

• You may only use constant extra space.
• You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).

For example,
Given the following perfect binary tree,

     1
/  \
2    3
/ \  / \
4  5  6  7


After calling your function, the tree should look like:

     1 -> NULL
/  \
2 -> 3 -> NULL
/ \  / \
4->5->6->7 -> NULL


    public class TreeLinkNode {        int val;        TreeLinkNode left, right, next;        TreeLinkNode(int x) {            val = x;        }    }    public void connect(TreeLinkNode root) {        if (root == null) {            return;        }        if (root.left != null && root.right != null) {            root.left.next = root.right;        }        if (root.next != null && root.next.left != null) {            root.right.next = root.next.left;        }        connect(root.left);        connect(root.right);    }

# Same Tree

Given two binary trees, write a function to check if they are equal or not.

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

    public boolean isSameTree(TreeNode p, TreeNode q) {        if (p == null && q == null) {            return true;        } else if (p == null || q == null) {            return false;        }        return p.val == q.val && isSameTree(p.left, q.left)                && isSameTree(p.right, q.right);    }

# Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree is symmetric:

    1   / \  2   2 / \ / \3  4 4  3

But the following is not:

    1   / \  2   2   \   \    3   3

Note:
Bonus points if you could solve it both recursively and iteratively.

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

    // recursively    public boolean isSymmetric(TreeNode root) {        if (root == null) {            return true;        }        return isSymmetric(root.left, root.right);    }    boolean isSymmetric(TreeNode p, TreeNode q) {        if (p == null && q == null) {            return true;        } else if (p == null || q == null) {            return false;        }        return p.val == q.val && isSymmetric(p.left, q.right)                && isSymmetric(p.right, q.left);    }

    // iteratively    public boolean isSymmetric2(TreeNode root) {        if (root == null) {            return true;        }        Deque<TreeNode> deque = new LinkedList<TreeNode>();        if (root.left == null && root.right == null) {            return true;        } else if (root.left == null || root.right == null) {            return false;        } else {            deque.addLast(root.left);            deque.addLast(root.right);        }        while (deque.size() != 0) {            TreeNode p = deque.pop();            TreeNode q = deque.pop();            if (p.val != q.val) {                return false;            }            if (p.left == null && q.right == null) {                // do nothing            } else if (p.left == null || q.right == null) {                return false;            } else {                deque.addLast(p.left);                deque.addLast(q.right);            }            if (p.right == null && q.left == null) {                // do nothing            } else if (p.right == null || q.left == null) {                return false;            } else {                deque.addLast(p.right);                deque.addLast(q.left);            }        }        return true;    }

# Sum Root to Leaf Numbers

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

For example,

    1   / \  2   3

The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.

Return the sum = 12 + 13 = 25.

    int sumNumbers(TreeNode root, int parentval) {        if (root == null) {            return 0;        }        int p = parentval * 10 + root.val;        if (root.left == null && root.right == null) {            return p;        }        return sumNumbers(root.left, p) + sumNumbers(root.right, p);    }

# Validate Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees must also be binary search trees.

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

    boolean failed = false;    // 要用long，而不是int    // 否则涉及到Integer.MIN_VALUE的用例会出现错误    // 比如{Integer.MIN_VALUE}这个用例会错误    long last = Long.MIN_VALUE;    public boolean isValidBST(TreeNode root) {        if (root == null) {            return true;        }        inorder(root);        return !failed;    }    private void inorder(TreeNode root) {        if (root == null || failed) {            return;        }        // 左        inorder(root.left);        // 中，相当于中序遍历中的打印操作        // 只采用了一个变量，所以空间复杂度是O(1)        // 传统的做法是建立一个ArrayList，然后判断中序遍历是否是递增的，但是空间复杂度是O(n)        if (last >= root.val) {            failed = true;        }        last = root.val;        // 右        inorder(root.right);    }

• 私有
• 公开
• 删除