从遍历Dom树,初识算法

参考文章:https://juejin.im/post/6844903731973062669

目的：自定义一个方法去检查DOM中的某个元素

    // HTML结构如下
    <div class="wrapper">
        <section class="header">
            <div class="logo"></div>
        </section>
        <section class="main">
            <div class="sidebar">
                <ul class="menu">
                    <li class='li'>
                        <a href="" id='demo'>li1-a</a>
                    </li>
                    <li class='li'>
                        <a href="">li2</a>
                    </li>
                </ul>
            </div>
        </section>
        <section class="footer">
            <div class="copyright"></div>
        </section>
    </div>

思路和方案:

1. 深度遍历，利用递归实现
2. 使用栈，深度优先
3. 广度优先，非递归实现

深度遍历,利用递归实现

    const cusGetElementByIdByDFS = function(parentNode, id) {
        if(parentNode){
            let target = null
            const children = Array.from(parentNode.children)
            if(parentNode.id === id) {
                return parentNode
            }
            for(let i =0; i < children.length; i++){
                target = cusGetElementByIdByDFS(children[i], id)
                if(target) {
                    return target
                }
            }
        }
        return null
    }

使用栈，深度优先

    const cusGetElementByIdByDFS2 = function(parentNode, id) {
        if(!parentNode) {
            return null
        }
        let stack = []
        if(parentNode.id === id) {
            return parentNode
        }
        parentNode.forEach(item =>{
            stack.push(item)
        })
        while(stack.length > 0) {
            let node = stack.pop()
            if(node.id === id){
                return node
            } else {
                if(node.children.length > 0) {
                    stack = Array.from(node.children).concat(stack)
                }
            }
        }
    }

广度优先，非递归实现

    const cusGetElementByIdByDFS2 = function(parentNode, id) {
        
        const layer = [] 
        
        if ( parentNode ) {
            layer.push({
                node:parentNode,
                dep:1
            })

            while( layer.length > 0 ){
                let root = layer.shift()    // 出队列
                if(root.id === id) {
                    return root
                } else {
                    if(root.children.length > 0) {
                        Array.from(root.children).forEach(node=>{
                             layer.push({
                                node,
                                dep: item.dep++
                            })
                        })
                       
                    }
                }
            }    
        }

        return null
    }