Binary Tree Paths

update Jun 28, 2017

leetcode

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"]

分析

这道题目应该很经典，要输出所有的path，我们就需要在每层recursion中传入当前node之前的路径，也就是path。明白了这一点之后，这个问题几乎就变成了简单的dfs或者bfs。在这里，我记录三种实现，分别是recursive dfs，dfs with stack and bfs with queue。

Recursive DFS

Python Code：

    # dfs recursive
    class Solution(object):
        def binaryTreePaths(self, root):
            """
            :type root: TreeNode
            :rtype: List[str]
            """
            def dfs(root, path):
                if root is None:
                    return
                if root.left is None and root.right is None:
                    res.append(path + str(root.val))
                    return
                if root.left:
                    dfs(root.left, path + str(root.val) + '->')
                if root.right:
                    dfs(root.right, path + str(root.val) + '->')

            res = []
            dfs(root, '')
            return res

DFS with Stack

相当于是一个 iterative 的 preorder traversal，但是用stack记录另一个变量：path。那么对于每个刚出stack的node来说，我们可以用它的左右孩子和他的path继续向下遍历。

Python Code:

    class Solution(object):
        def binaryTreePaths(self, root):
            """
            :type root: TreeNode
            :rtype: List[str]
            """
            if not root:
                return []
            res, stack = [], [(root, '')]
            # python 的list可以轻松存放tuple，如果是java则需要使用两个stack,
            # 或者用内部类
            while stack:
                node, path = stack.pop()
                if not node.left and not node.right:
                    res.append(path + str(node.val))
                if node.left:
                    stack.append((node.left, path + str(node.val) + '->'))
                if node.right:
                    stack.append((node.right, path + str(node.val) + '->'))
            return res

Java Code

    // using stack
    private class Path { // inner class
        String path;
        TreeNode node;
        public Path(String path, TreeNode node) {
            this.path = path;
            this.node = node;
        }
    }
    public List<String> binaryTreePaths(TreeNode root) {
        Deque<Path> stack = new LinkedList<>(); // stack of inner class
        List<String> res = new ArrayList<>();
        if (root == null) return res;
        stack.addLast(new Path(root.val + "", root));
        while (stack.size() > 0) {
            TreeNode node = stack.peekLast().node;
            String path = stack.peekLast().path;
            stack.removeLast();
            if (node.left == null && node.right == null) {
                res.add(path);
                continue;
            }
            if (node.left != null) {
                stack.addLast(new Path(path + "->" + node.left.val, node.left));
            }
            if (node.right != null) {
                stack.addLast(new Path(path + "->" + node.right.val, node.right));
            }
        }
        return res;
    }

BFS with Queue

Python code:

    class Solution:
        def binaryTreePaths(self, root):
            """
            :type root: TreeNode
            :rtype: List[str]
            """
            if not root: return []
            queue = collections.deque()
            res = []
            queue.appendleft((root, str(root.val)))
            while queue:
                node, path = queue.pop()
                if not node.left and not node.right:
                    res.append(path)
                if node.left:
                    queue.appendleft((node.left, path + "->" + str(node.left.val)))
                if node.right:
                    queue.appendleft((node.right, path + "->" + str(node.right.val)))
            return res

update Jul 14, 2017 14:17

更新：九章算法中的思路

学习了九章，他们强调对于这类题目有两种思路，分别是traverse法和分治法。前者比较类似之前的第一种python实现，利用全局变量res记录paths，然后随着遍历逐个node更新path，当走到leaf的时候把path加入res。后者则是利用同一个问题对于左右子树的结论去推导最终结论。对于这道题，先得到左右子树所有的paths，然后在他们前面加上当前node.val（用for loop）。

java 实现：

     // traverse 法
     class Solution {
        public List<String> binaryTreePaths(TreeNode root) {
            List<String> res = new ArrayList<>();
            dfs(root, "", res);
            return res;
        }
        private void dfs(TreeNode root, String path, List<String> res) {
            if (root == null) return;
            if (root.left == null && root.right == null) {
                res.add(path + root.val);
                return;
            }
            dfs(root.left, path + root.val + "->", res);
            dfs(root.right, path + root.val + "->", res);
        }
    }

    // 分治 法
    class Solution {
        public List<String> binaryTreePaths(TreeNode root) {
            List<String> res = new ArrayList<>();
            if (root == null) return res;
            if (root.left == null && root.right == null) {
                res.add("" + root.val);
                return res;
            }
            res.addAll(binaryTreePaths(root.left));
            res.addAll(binaryTreePaths(root.right));
            for (int i = 0; i < res.size(); ++i) {
                res.set(i, root.val + "->" + res.get(i));
            }
            return res;
        }
    }

C++ 实现：

// traverse
class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> res;
        dfs(root, "", res);
        return res;
    }

    void dfs(TreeNode* root, string path, vector<string>& res) {
        if (root == nullptr) return;
        else if (root->left == nullptr && root->right == nullptr) {
            res.push_back(path + to_string(root->val));
            return;
        }
        path += to_string(root->val) + "->" ;
        dfs(root->left, path, res);
        dfs(root->right, path, res);
    }
};

// 分治法
class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> res;
        if (root == nullptr) return res;
        vector<string> left = binaryTreePaths(root->left);
        vector<string> right = binaryTreePaths(root->right);
        if (left.empty() && right.empty()) {
            res.push_back(to_string(root->val));
        }
        for (string path : left) {
            res.push_back(to_string(root->val) + "->" + path);
        }
        for (string path : right) {
            res.push_back(to_string(root->val) + "->" + path);
        }
        return res;
    }
};