【day08】LeetCode（力扣）每日一刷[409. 最长回文串 ][144. 二叉树的前序遍历][589. N 叉树的前序遍历 ]

class Solution {
    public int longestPalindrome(String s) {
        char[] arr = s.toCharArray();//字符串转为数组，每个元素都是字符串中的一个字符
        Map<Character,Integer> map = new HashMap<>();//创建双列集合map
        for(char c :arr ){//增强for循环，遍历数组
            if(map.containsKey(c)){//如果字符存在，出现次数value值+1
                map.replace(c,map.get(c).intValue()+1);
            }else{//如果字符不在集合中，创建集合，主键为字符，value值为出现次数1
                map.put(c,1);
            }
        }

        int len = 0;//表示回文串长度
        //实用迭代器Iterator遍历集合元素
        Iterator<Map.Entry<Character,Integer>> iterator = map.entrySet().iterator();
        while(iterator.hasNext()){
            Map.Entry<Character,Integer> entry = iterator.next();
            len += entry.getValue()/2*2;//可以使用该字符 v / 2 * 2 次
            if(len%2==0 && entry.getValue()%2 ==1)//第一个出现的奇数次的元素作为回文串唯一中心
            len++;
        }
        return len;
    }
}

class Solution {
    public int longestPalindrome(String s) {
        int[] count = new int[128];
        int length = s.length();
        for (int i = 0; i < length; ++i) {
            char c = s.charAt(i);
            count[c]++;
        }

        int ans = 0;
        for (int v: count) {
            ans += v / 2 * 2;
            if (v % 2 == 1 && ans % 2 == 0) {
                ans++;
            }
        }
        return ans;
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List list = new ArrayList();  //创建list集合，用于存放先序遍历的节点元素
        if(root == null) return list; //如果根节点为空，直接返回空的集合
        TreeNode node = root;         //获取根节点
        //创建堆结构
        Deque<TreeNode> stack = new LinkedList<>();
        //当堆不为空或二叉树节点不为空时
        while(!stack.isEmpty() || node != null){
            while(node != null){      //树节点不为空
                list.add(node.val);   //节点元素传入集合
                stack.push(node);     //同时节点如栈
                node = node.left;     //堆节点左孩子重复操作
                //当左子树所有的左孩子入栈，代表遍历完左子树的所有子节点
            }
            //堆顶节点出栈
            node = stack.pop();
            //循环遍历出栈节点的右孩子
            node = node.right;
        }
        return list;                  //返回存放先序遍历节点顺序的集合
    }
}

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
    public List<Integer> preorder(Node root) {
        List list = new ArrayList(); //创建集合存放先序遍历后的节点
        if(root == null) return list;//根节点为空，直接返回空集合

        Deque<Node> stack = new LinkedList<>();//创建堆结构
        stack.push(root);                      //根节点入栈
        while(!stack.isEmpty()){               //只要栈不为空
            Node curr = stack.pop();           //堆顶元素出栈
            list.add(curr.val);                //同时记录进集合
            //将出栈节点的子节点按照逆序入栈，当下一次出栈时，记录的就是左孩子
            for(int i = curr.children.size()-1;i>=0;--i){
                stack.push(curr.children.get(i));
            }
            //重读操作
        }
        return list;
    }
}