BinaryTreePreorderTraversal [source code]

public class BinaryTreePreorderTraversal {
static
/******************************************************************************/
public class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null)
            return res;
        Stack<TreeNode> s = new Stack<>();
        s.push(root);
        while (!s.isEmpty()) {
            TreeNode cur = s.pop();
            res.add(cur.val);
            if (cur.right != null)
                s.push(cur.right);
            if (cur.left != null)
                s.push(cur.left);
        }
        return res;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        BinaryTreePreorderTraversal.Solution tester = new BinaryTreePreorderTraversal.Solution();
    }
}

很熟悉了, 直接做出来; 速度是1ms (23%)

然后尝试用Morris写的一个, 放在这里:

public class Solution {  
    public List<Integer> preorderTraversal(TreeNode root) {  
        List<Integer> res = new ArrayList<>();  
        if (root == null)  
            return res;  
        TreeNode cur = root;  
        while (cur != null) {  
            if (cur.left == null) {  
                res.add(cur.val);  
                cur = cur.right;  
            } else {  
                TreeNode prev = cur.left;  
                while (prev.right != null && prev.right != cur)  
                    prev = prev.right;  
                if (prev.right == null) {  
                    res.add(cur.val);  
                    prev.right = cur;  
                    cur = cur.left;  
                } else {  
                    prev.right = null;  
                    cur = cur.right;  
                }  
            }  
        }  
        return res;  
    }  
}

速度是一样的;

这个是discussion最优解:

public List<Integer> preorderTraversal(TreeNode node) {  
    List<Integer> list = new LinkedList<Integer>();  
    Stack<TreeNode> rights = new Stack<TreeNode>();  
    while(node != null) {  
        list.add(node.val);  
        if (node.right != null) {  
            rights.push(node.right);  
        }  
        node = node.left;  
        if (node == null && !rights.isEmpty()) {  
            node = rights.pop();  
        }  
    }  
    return list;  
}

跟我自己写的ver1也就是traversal-oriented的做法是类似的, 但是不完全类似; 我从讲义上面看到的那个ver1, 其实本质上还是一个stack-oriented; 这里他这个才更像是一个标准的traversal-oriented的思路;

这个是对上面算法的直观改写:

public List<Integer> preorderTraversal(TreeNode root) {  
    List<Integer> result = new LinkedList<>();  
    Deque<TreeNode> stack = new LinkedList<>();  
    TreeNode node = root;  
    while (node != null || !stack.isEmpty()) {  
        if (node != null) {  
            result.add(node.val);  
            stack.push(node.right);  
            node = node.left;  
        } else {  
            node = stack.pop();  
        }  
    }  
    return result;  
}

另外底下回复展开了对复杂度的讨论, 时间是N这个是没有问题的, 但是Stack的做法, 空间其实未必就是N的, WorstCase才是, BestCase好像也可以是O(1)? 比如一个全体往左的line的; 类似的, 如果是一个往右的line, 那么就是WorstCase, 也就是O(N)了;

注意这种复杂度的讨论的前提是N指的是number of nodes而不是height; 不过既然是复杂度, 那么就是要measure input size, 用nodes number好像更合理一些;

这个是对我的ver2的直观改写:

public List<Integer> preorderTraversal(TreeNode root) {  
    List<Integer> result = new LinkedList<>();  
    Deque<TreeNode> stack = new LinkedList<>();  
    stack.push(root);  
    while (!stack.isEmpty()) {  
        TreeNode node = stack.pop();  
        if (node != null) {  
            result.add(node.val);  
            stack.push(node.right);  
            stack.push(node.left);  
        }  
    }  
    return result;  
}

其实唯一的差别也就是when to process null: at leaf or just above leaf;

除开这些好像也没有什么其他的特别好的做法了;

在bittiger的视频上面看到一个无敌的解法:

class Solution {  
    public List<Integer> preorderTraversal(TreeNode root) {  
        List<Integer> res = new ArrayList<> ();  
        Deque<Operation> stack = new ArrayDeque<> ();  
        stack.push (new Operation (0, root));  
        while (!stack.isEmpty ()) {  
            Operation cur = stack.pop ();  
            if (cur.node == null)  
                continue;       // defensive coding, or leaf handling  
            if (cur.action == 1) {  
                res.add (cur.node.val);  
            } else {  
                stack.push (new Operation (0, cur.node.right));  
                stack.push (new Operation (0, cur.node.left));  
                stack.push (new Operation (1, cur.node));  
            }  
        }  
        return res;  
    }  

    static class Operation {  
        // 0 for visit (not print, just pass-by); 1 for print (actually visit this node).   
        // Another way of thinking: or 1 for actually visit this node, 0 for NOT visit.  
        int action;  
        TreeNode node;  
        Operation (int a, TreeNode n) {  
            action = a;  
            node = n;  
        }  
    }  
}

这个解法的无敌之处在于, 你的Stack循环里面每一个iteration反正处理的是一个node, 但是实际上当你手上有这个node的时候, 实际上你的可行性的做法是, 可能你并不visit他(就是这里的0), 也可能你认为应该visit了(对应是1); 所以这样一个flag其实就是控制你在node的时候, 是真的去处理他, 还是去跳过, 类似一个defer的操作;

这个解法的无敌之处在于, 把那三个push的操作稍微调换一下, InOrder和PostOrder直接一样的解法, 真的是大开眼界;

Problem Description

Given a binary tree, return the preorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},

   1  
    \  
     2  
    /  
   3

return [1,2,3].

Note: Recursive solution is trivial, could you do it iteratively?

Difficulty:Medium
Total Accepted:186.7K
Total Submissions:415.3K
Contributor: LeetCode
Related Topics
tree stack
Similar Questions
Binary Tree Inorder Traversal Verify Preorder Sequence in Binary Search Tree