三序遍历，vertical order

Binary Tree Preorder Traversal

• preorder 直接用 stack;

• inorder 用 stack + cur;

• postorder 用 stack + cur + prev;

• 递归 ✓

• 迭代 ✓

• parent ✓

• 复杂度 ✓

迭代的写法过于 trivial 就不细说了，记得因为 stack 先入后出的特点，push 的时候先 push 右边的就行。

public class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        if(root != null) stack.push(root);

        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            list.add(node.val);
            // Remember to reverse order.. right -> left
            if(node.right != null) stack.push(node.right);
            if(node.left != null) stack.push(node.left);
        }

        return list;
    }
}

头一次写带 parent 指针的写法还挺不习惯的。。改了好一会儿。我觉得这个博客写的思路不错，不过要注意这哥们的代码有 bug，root 为 1，左面一条线连到 2 , 3 然后 1 的右孩子为 4 的情况，这个代码只能返回 1,2,3，看不到 4.

https://haixiaoyang.wordpress.com/2012/04/06/pre-order-traverse-of-a-binary-tree-with-parent-pointer/

在写 parent 指针遍历的时候，应该多想想 stack 写法每次 pop 的回溯位置，是很重要的参考。

测试了几个 case 没有问题的代码：

• 以 cur != null 为 while 循环条件；

• 直接输出 cur.val

• cur 左面有东西就 cur = cur.left;

• 左面没有但右面有，cur = cur.right;

• 其他情况就属于要往上回溯了，注意这个回溯长度可以是任意的，我们要注意把 cur 放到正确的位置上。

• 我们要找的位置相对于从左往上的路线而言，是 cur 往上看第一个右节点不为 null 的地方；相对于从右往上的路线而言就是无脑往上走直到走向成从左往上为止。

• 在任何时刻追溯完毕发现 cur.parent 为空，说明走完了。

• 否则 cur 就是 cur.parent.right.

追溯流程主要就是图中这两步。

     public static void printPreorder(TreeNode root) {
        TreeNode cur = root;
        while(cur != null){
            System.out.println(cur.val);

            if(cur.left != null){
                cur = cur.left;
            } else if(cur.right != null){
                cur = cur.right;
            } else {
                while(cur.parent != null && (cur.parent.right == null || cur == cur.parent.right)){
                    cur = cur.parent;
                }
                if(cur.parent == null) break;
                cur = cur.parent.right;
            }
        }
    }

Binary Tree Inorder Traversal

• preorder 直接用 stack;

• inorder 用 stack + cur;

• postorder 用 stack + cur + prev;

• 递归 ✓

• 迭代 ✓

• parent

• 复杂度 ✓

stack 写法要记住的细节是，两个 while 循环里都是 cur != null

 public class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        Stack<TreeNode> stack = new Stack<TreeNode>();

        TreeNode cur = root;
        while(cur != null || !stack.isEmpty()){
            while(cur != null){
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode node = stack.pop();
            list.add(node.val);
            cur = node.right;
        }

        return list;
    }
}

In-order 的 parent 指针写法稍微 tricky 一些，考虑到 in-order 的特性和面经问到的内容，我写了两个函数，主要是 getSuccessor()，然后把 root 放到二叉树最左面为起点依次调用。

getSuccessor() 流程，其实有点像 morris - traversal:

• 如果 cur 右子树不为空，返回右子树里面最左面的点(也即 cur.right 一路向左最远的点)

• 否则一路沿着(右child - parent) 的路线往上走，然后返回 parent 就行了。

  public static void printInorder(TreeNode root) {
       TreeNode cur = root;
       while(cur.left != null){
           cur = cur.left;
       }
       // Now current is at left most pos
       while(cur != null){
           System.out.println(cur.val);
           cur = getSuccessor(cur);
       }
   }
  
   private static TreeNode getSuccessor(TreeNode cur){
       // Find leftmost node in right subtree
       if(cur.right != null){
           cur = cur.right;
           while(cur.left != null) cur = cur.left;
       } else {
       //
           while(cur.parent != null && cur == cur.parent.right){
               cur = cur.parent;
           }
           if(cur.parent == null) return null;
  
           cur = cur.parent;
       }
       return cur;
   }

Inorder Successor in BST

这题没 parent pointer,给的也只是 root，但是还算挺有意思的，和上一题有联系。BST 的好处是在任意 node 上都可以通过与目标值比大小来确定方向， 因此就有比较简洁的迭代写法。

BST 里面，任意位置，任意楼层，都可以通过 value 的比较确定相对位置，这是 BST 一个最好用的性质。

因此在 BST 里面，确定起来就很简单了，从 root 往下走，每次往左拐的时候，存一下，记录着最近一个看到的比 p.val 大的 node 就行了。

public class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        TreeNode rst = null;

        while(root != null){
            if(root.val > p.val){
                rst = root;
                root = root.left;
            } else {
                root = root.right;
            }
        }

        return rst;
    }
}

顺着这个思路讲，BST 里面找 in-order predecessor 也特简单，这次往左走的时候不记，往右走的时候记，就行了。

public class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        TreeNode rst = null;

        while(root != null){
            if(root.val > p.val){
                root = root.left;
            } else {
                rst = root;
                root = root.right;
            }
        }

        return rst;
    }
}

Binary Tree Postorder Traversal

这题是二叉树遍历里面迭代写起来最麻烦的一个，迭代写法在 LeetCode 的标注难度是 Hard.

• 6/5 复习时候写错了，第一个地方是 post order 因为每一步用 stack 顶元素作为新的 cur，在 while 循环中只需要以 !stack.isEmpty() 为条件去判断。第二点是， post-order 是【左，右，中】，压栈的时候还是先看左再看右的，顺序不能错。

• post order 遍历中最重要的是 prev 与 cur 的相对关系，相当于存了上一步的动作，用作下一步的方向。

• 用一个 stack 存着所有的 candidate node，栈顶为当前 candidate，并且以栈是否为空做唯一判断标准（还有没有要看的 candidate）

  public class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
  
        TreeNode cur = root;
        TreeNode prev = null;
        if(root != null) stack.push(root);
  
        while(!stack.isEmpty()){
            cur = stack.peek();
  
            // cur 在 prev 下面，要尝试探索所有 cur 下面的节点
            // 如果 cur 是叶节点的话，会在最后把 prev 赋值成 cur，再下一轮的时候被 pop 掉。
            if(prev == null || prev.left == cur || prev.right == cur){
                if(cur.left != null){
                    stack.push(cur.left);
                } else if(cur.right != null){
                    stack.push(cur.right);
                }
            } else if(cur.left == prev){
            // 刚把左边处理完回来，看看右边还有没有节点
                if(cur.right != null) stack.push(cur.right);
            } else {
            // 左右子树都处理完了，处理当前节点。
                list.add(cur.val);
                stack.pop();
            }
            prev = cur;
        }
  
        return list;
    }
  }

  这题还有一种比较耍流氓的写法，因为太过 trivial 就不当做这题的重点去提了。。。。

这种写法的主要缺点是，当 tree 非常大我们只需要输出正确结果时，reverse list 的写法必须依赖于存储所有的

• 对于给定序列 S，定义 S' 为反序序列

• 定义 R 为 root node 序列，有 R = R'

• 定义 C 为子节点序列，正确顺序为“左-右”

• 那么 post order 的序列顺序为 CR

• 如果在做pre order时生成 RC' 序列，那么反序之后可以得到 (RC')' = CR' = CR = post order 序列。

  public class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
  
        if(root != null) stack.push(root);
  
        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            list.add(node.val);
            if(node.left != null) stack.push(node.left);
            if(node.right != null) stack.push(node.right);
        }
        Collections.reverse(list);
        return list;
    }
  }

Binary Tree Vertical Order Traversal

• 以 root 为原点，每次左走一步为 offset -1 ，右走一步为 offset +1，把所有 offset 相等的 node 放到一个 list 里。

这题我一个不成功的尝试是用 dfs 解决。代码上讲 dfs 可以得到所有的 List 并且里面包含所有正确元素，但是无论是 preorder , inorder 还是 postorder，我们不能保证每一个 list 里的元素顺序是正确的，因为可能某一个子树沿着另一边走的很远，导致 dfs 时先把这个点加了进去。

因此为了保证正确顺序，还是得用 bfs，level order traversal.

Map 的选择上可以用 HashMap 或者 TreeMap 都可以，TreeMap 里因为 key 默认是排序的遍历起来省事一些，不过 insert 的时间复杂度更高，导致速度变慢，不如记录 index 里面 key 的范围然后遍历时间上经济。

  public class Solution {
      private class Tuple{
        TreeNode node;
        int index;
        public Tuple(TreeNode node, int index){
            this.node = node;
            this.index = index;
        }
      }

      public List<List<Integer>> verticalOrder(TreeNode root) {
        List<List<Integer>> rst = new ArrayList<List<Integer>>();
        Map<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();

        Queue<Tuple> queue = new LinkedList<Tuple>();
        if(root != null) queue.offer(new Tuple(root, 0));
        int min = 0;
        int max = 0;
        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i = 0; i < size; i++){
                Tuple tuple = queue.poll();
                min = Math.min(min, tuple.index);               
                max = Math.max(max, tuple.index);
                if(!map.containsKey(tuple.index)){
                    List<Integer> list = new ArrayList<Integer>();
                    list.add(tuple.node.val);
                    map.put(tuple.index, list);
                } else {
                    map.get(tuple.index).add(tuple.node.val);
                }

                if(tuple.node.left != null) queue.offer(new Tuple(tuple.node.left, tuple.index - 1));
                if(tuple.node.right != null) queue.offer(new Tuple(tuple.node.right, tuple.index + 1));
            }
        }

        for(int i = min; i <= max; i++){
              if(map.containsKey(i))  rst.add(map.get(i));
        }

        return rst;
    }
}