算法题-将Android的view内的控件全部涂成红色

算法

coffee

解题思路

分析需求，Android的view是树形结构，所以问题可以转换成树的遍历。
树的遍历分为递归和非递归，面试通常要求用非递归实现

递归

1
2
3
4
5
6
7
8
9
public void recurTraverse(View v) {
    v.setBackgroundColor(0xF00);
    if (v instanceof ViewGroup) {
        ViewGroup group = (ViewGroup) v;
        for (int i = 0, len = group.getChildCount(); i < len; i++) {
            recurTraverse(group.getChildAt(i));
        }
    }
}

非递归

递归遍历的问题在于方法调用本身存在一个函数栈，如果树的层级特别深，程序会存在栈溢出的风险StackOverflowException.
树的非递归遍历有多种方式，主要是栈和队列的应用，这里使用层序遍历的方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public void unRecurTraverse(View v) {
    Queue<View> queue = new LinkedList<>();
    queue.offer(v);
    while (!queue.isEmpty()) {
        View view = queue.poll();
        view.setBackgroundColor(0xF00);
        if (v instanceof ViewGroup) {
            ViewGroup group = (ViewGroup) v;
            for (int i = 0, len = group.getChildCount(); i < len; i++) {
                View child = group.getChildAt(i);
                queue.offer(child);
            }
        }
    }
}