算法之深度优先搜素（DFS）和广度优先搜素（BFS）

古城微笑少年丶 2021-12-14 09:43 253阅读 0赞

深度优先搜素（DFS）：如果当前节点有孩子，遍历当前孩子的孩子再遍历兄弟节点的孩子（一条路走到头再回来走另一条）。

**HTML 代码**
    <div class="root">
    	<div class="items">
    		<ol>
    			<li class="list-item">a</li>
    		</ol>
    		<div class="item">
    			<span>aaa</span>
    		</div>
    	</div>
    </div>

// 深度优先搜索 递归版
    <script>
    	function DFS(node, list) {
    		if (node) {
    			list.push(node);
    			var child = node.children;
    			// 如果存在孩子，对每个孩子再进行递归搜索
    			for (var i = 0; i < child.length; i++) {
    				DFS(child[i], list);
    			}
    		}
    		return list;
    	}
    	var root = document.querySelector('.root');
    	var list = [];
    	console.log(DFS(root, list));
    </script>

输出为： \[div.root, div.items, ol, li.list-item, div.item, span\]

广度优先搜索：先遍历根节点的所有孩子，再遍历所有孩子的孩子（一层一层的往外走）

输出为： \[div.root, div.items, ol, div.item, li.list-item, span\]

扩展：  
输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)  
用例:  
\{10,5,12,4,7\},22

对应输出应该为:

\[\[10,5,7\],\[10,12\]\]

/* function TreeNode(x) {
        this.val = x;
        this.left = null;
        this.right = null;
    } */
    function FindPath(root, expectNumber)
    {
        // write code here
        // 深度优先搜索求和问题
        var result = [];
        if (!root) {
            return result;
        }
        DFS(root, expectNumber, [], 0, result);
        return result;
    }
    
    function DFS(root, expectNumber, path, currentSum, result) {
        currentSum += root.val;
        path.push(root.val);
        if (currentSum === expectNumber && root.left === null && root.right === null) {
            result.push(path.slice(0));
        }
        if (root.left) {
            DFS(root.left, expectNumber, path, currentSum, result);
        }
        if (root.right) {
            DFS(root.right, expectNumber, path, currentSum, result);
        }
        // 每次清空数组
        path.pop();
    }