314.Binary-Tree-Vertical-Order-Traversal

314. Binary Tree Vertical Order Traversal

题目地址

https://leetcode.com/problems/binary-tree-vertical-order-traversal/

题目描述

Given a binary tree, return the vertical order traversal of its nodes' values. (ie, from top to bottom, column by column).

If two nodes are in the same row and column, the order should be from left to right.

Examples 1:

Input: [3,9,20,null,null,15,7]

   3
  /\
 /  \
 9  20
    /\
   /  \
  15   7 

Output:

[
  [9],
  [3,15],
  [20],
  [7]
]
Examples 2:

Input: [3,9,8,4,0,1,7]

     3
    /\
   /  \
   9   8
  /\  /\
 /  \/  \
 4  01   7 

Output:

[
  [4],
  [9],
  [3,0,1],
  [8],
  [7]
]

代码

Approach 1[Accpeted]: DFS

1. Traverse to find the minimum and maximum vertical levels

2. 双Queue进行DFS层序遍历，另一个Queue放level

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int min, max;
    public List<List<Integer>> verticalOrder(TreeNode root) {
        findMinMax(root, 0);
        List<List<Integer>> ans = new ArrayList<>();
    if (root == null) return ans;

        for (int i = min; i <= max; i++) {
            List<Integer> list = new ArrayList<Integer>();
            ans.add(list);
        }

        Queue<TreeNode> nodeQ = new LinkedList<TreeNode>();
        Queue<Integer> levelQ = new LinkedList<Integer>();
        nodeQ.add(root);
        levelQ.add(0 - min);
        while (!nodeQ.isEmpty()) {
            int size = nodeQ.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = nodeQ.poll();
                int index = levelQ.poll();
                List<Integer> list = ans.get(index);
                list.add(node.val);

                if (node.left != null) {
                    nodeQ.add(node.left);
                    levelQ.add(index - 1);
                }
                if (node.right != null) {
                    nodeQ.add(node.right);
                    levelQ.add(index + 1);
                }
            }
        }
        return ans;
    }

    void findMinMax(TreeNode root, int hd) {
        if (root == null)    return;

        if (hd < min) {
            min = hd;
        }
        if (hd > max) {
            max = hd;
        }

        findMinMax(root.left, hd - 1);
        findMinMax(root.right, hd + 1);
    }

}

Approach 2[Rejected]: preorder Iterative

class Solution {
    int min, max;
    public List<List<Integer>> verticalOrder(TreeNode root) {
        findMinMax(root, 0);
        List<List<Integer>> ans = new ArrayList<>();
        for (int i = min; i <= max; i++) {
            List<Integer> list = new ArrayList<Integer>();
            ans.add(list);
        }

    Stack<TreeNode> stack = new Stack<TreeNode>();
        Stack<Integer> indexStack = new Stack<Integer>();
        stack.push(root);
        indexStack.push(0);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            int index = indexStack.pop();
            List<Integer> list = ans.get(index - min);

            System.out.print(" " + node.val);
            list.add(node.val);

            if (node.right != null) {
                stack.push(node.right);
                indexStack.push(index + 1);
            }

            if (node.left != null) {
                stack.push(node.left);
                indexStack.push(index - 1);
            }

        }

            return ans;
    }

    void findMinMax(TreeNode root, int hd) {
        if (root == null)    return;

        if (hd < min) {
            min = hd;
        }
        if (hd > max) {
            max = hd;
        }

        findMinMax(root.left, hd - 1);
        findMinMax(root.right, hd + 1);
    }
}

Approach 3[Rejected]: preorder in Recursion

class Solution {
    int min;
    int max;
    public List<List<Integer>> verticalOrder(TreeNode root) {

        findMinMax(root, 0);
        List<List<Integer>> ans = new ArrayList<>();
        for (int i = min; i <= max; i++) {
            List<Integer> list = new ArrayList<Integer>();
            traverseVerticalNode(root, i, 0, list);
            ans.add(list);
        }

        return ans;
    }

    void findMinMax(TreeNode root, int hd) {
        if (root == null)    return;

        if (hd < min) {
            min = hd;
        }
        if (hd > max) {
            max = hd;
        }

        findMinMax(root.left, hd - 1);
        findMinMax(root.right, hd + 1);
    }

    void traverseVerticalNode(TreeNode root, int line, int hd, List<Integer> list) {
        if (root == null) return;

        if (line == hd) {
            list.add(root.val);
        }

        traverseVerticalNode(root.left, line, hd - 1, list);
        traverseVerticalNode(root.right, line, hd + 1, list);
    }
}