# PreOrder, InOrder, PostOrder

Given a non-empty array of integers, every element appears twice except for one. Find that single one.

Input: [1, 2, 2, 3, 3]
Output: 1

Input: [4, 1, 2, 1, 2]
Output: 4

Input: [1, 2, 1, 2]
Output: -1

public int singleNumber(int[] nums) {
 
     Map<Integer, Integer> map = new HashMap();
  
     for (int i: nums) {
        if (map.containsKey(i)) {
            map.put(i, map.get(i) + 1);
        } else {
            map.put(i, 1);
        }
     }
     
//     for (int i : nums) {
//         map.put(i, map.getOrDefault(i, 0) + 1);
//     }

     for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
         if (entry.getValue() == 1) {
            return entry.getKey();
         }
     }
 
    return -1;
    
}

Given an array of strings, group anagrams together.

Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

Arrays.sort(charArr)
["eat", "tea", "tan", "ate", "nat", "bat"]
N is the length of the input array
M is the length of the longest character
["aet", "aet", "ant", "aet", "ant", "atb"]
N * MLog(M)

public List<List<String>> groupAnagrams(String[] strs) {
    if (strs == null || strs.length == 0) {
        return new ArrayList<>();
    }
    
    Map<String, List<String>> map = new HashMap<>();
    for (String str : strs) {
        char[] charArr = str.toCharArray();
        Arrays.sort(charArr);
        String key = String.valueOf(charArr);
        
        if (!map.containsKey(key)) {
            map.put(key, new ArrayList<>());
        }
        
        map.get(key).add(str);
    }
    
    List<List<String>> result = new ArrayList<>();
    for (List<String> strList : map.values()) {
        result.add(strList);
    }
    
    return result;
}

https://leetcode.com/problems/binary-tree-preorder-traversal/
https://leetcode.com/problems/binary-tree-inorder-traversal/
https://leetcode.com/problems/binary-tree-postorder-traversal/

1
/ \
2 3
/\ /\
4 5 6 7
PreOrder: 1,2,4,5,3,6,7
InOrder: 4,2,5,1,6,3,7
PostOrder: 4,5,2,6,7,3,1

PreOrder: while 裡面裡 加自己 推右邊 推左邊
InOrder: while 裡面while推到最左邊 結束後 加自己 換右邊
PostOrder: while 裡面裡 加自己到 index0 推左邊 推右邊

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
 
public List<Integer> preorderTraversal(TreeNode root) { 
    if (root == null) {
        return new ArrayList<>();
    }

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

ublic List<Integer> inorderTraversal(TreeNode root) { 
    if (root == null) {
        return new ArrayList<>();
    }

    List<Integer> result = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();

       if (node.right != null) {
           stack.push(node.right);
       }
       if (node.left != null) {
           stack.push(node.left);
       }
    }
    
    return result;
}

            1
           / \
          2  3 
         /\  /\
        4  5 6 7
 public List <Integer> inorderTraversal(TreeNode root) {
        List <Integer> res = new ArrayList<>();
        Stack <TreeNode> stack = new Stack<>();
        TreeNode curr = root;
        while (curr != null || !stack.isEmpty()) {
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }
            curr = stack.pop();
            res.add(curr.val);
            curr = curr.right;
        }
        return res;
    }
}

            1
           / \
          2  3 
         /\  /\
        4  5 6 7
res: 4, 5, 2, 1, 6, 7, 3
 public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root == null) return list;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()) {
            TreeNode curr = stack.pop();
            list.add(0,curr.val);
            if(curr.left!=null) {
              stack.push(curr.left);
            }
            if(curr.right!=null) {
               stack.push(curr.right); 
            }
        }
        return list;
    }