树简介

  • 分层数据的抽象模型 - DOM树，级联选择组件，树形控件
  • js没有树但是可以用Array和Object构建树

树的常用操作

  • 深度/广度优先遍历
  • 先中后序遍历

树的深度优先遍历（尽可能深的搜索树的分支—递归）

  2. const tree ={
  3.   val:'a',
  4.   children:[{
  5.     val:'b',
  6.       children:[{
  7.         val:'c',
  8.         children:[]
  9.       },{
  10.         val:'d',
  11.         children:[]
  12.       }]
  13.   },{
  14.     val:'e',
  15.       children:[{
  16.         val:'f',
  17.         children:[]
  18.       },{
  19.         val:'g',
  20.         children:[]
  21.       }]
  22.   }]
  23. }
  24.  let arr = [1,56,333];
  25.  console.log(arr.pop())
  27. const dfs = function(root){ 
  28.   console.log(root.val);
  29.   root.children.forEach((item)=>{
  30.     dfs(item)
  31.   })
  32. }
  33. dfs(tree)

树的广度优先遍历（优先遍历离根节点最近的节点）
1.新建一个队列，把根节点入队
2.对头出队并访问
3.把队头的children挨个入队
4.重复2，3直到队列为空

  1. const tree ={
  2.   val:'a',
  3.   children:[{
  4.     val:'b',
  5.       children:[{
  6.         val:'c',
  7.         children:[]
  8.       },{
  9.         val:'d',
  10.         children:[]
  11.       }]
  12.   },{
  13.     val:'e',
  14.       children:[{
  15.         val:'f',
  16.         children:[]
  17.       },{
  18.         val:'g',
  19.         children:[]
  20.       }]
  21.   }]
  22. }

二叉树

1.树的每个节点最多只能有两个子节点
2.js中通常用Object来模拟二叉树

  1. const binaryTree = {
  2.     val:'123',
  3.   left:{
  4.       val:55,
  5.     left:null,
  6.     right:null
  7.   },
  8.   right:{
  9.       val:66,
  10.     left:null,
  11.     right:null
  12.   }
  13. }

二叉树先序遍历（算法口诀）

1.访问根节点
2.对根节点的左子树进行先序遍历
3.对根节点的右子树进行先序遍历

  1. const bt = {
  2.     val:1,
  3.   left:{
  4.       val:2,
  5.     left:{
  6.         val:4,
  7.       left:null,
  8.       right:null
  9.     },
  10.     right:{
  11.       val:5,
  12.       left:null,
  13.       right:null
  14.     }  
  15.   },
  16.   right:{
  17.       val:3,
  18.     left:{
  19.         val:6,
  20.       left:null,
  21.       right:null
  22.     },
  23.     right:{
  24.       val:7,
  25.       left:null,
  26.       right:null
  27.     }  
  28.   }
  29. }
  31. const preorder = (root)=>{
  32.     if(!root){ return }
  33.   console.log(root.val);
  34.   preorder(root.left);
  35.   preorder(root.right);
  36. }
  37. preorder(bt)

二叉树中序遍历（算法口诀）

1.对根节点左子树进行中序遍历
2.访问根节点
3.对根节点的右子树进行中序遍历

  1. const bt = {
  2.     val:1,
  3.   left:{
  4.       val:2,
  5.     left:{
  6.         val:4,
  7.       left:null,
  8.       right:null
  9.     },
  10.     right:{
  11.       val:5,
  12.       left:null,
  13.       right:null
  14.     }  
  15.   },
  16.   right:{
  17.       val:3,
  18.     left:{
  19.         val:6,
  20.       left:null,
  21.       right:null
  22.     },
  23.     right:{
  24.       val:7,
  25.       left:null,
  26.       right:null
  27.     }  
  28.   }
  29. }
  31. const inorder = (root)=>{
  32.     if(!root){ return }
  33.   inorder(root.left);
  34.   console.log(root.val);
  35.   inorder(root.right);
  36. }
  37. inorder(bt)

二叉树中序遍历（算法口诀）

1.对根节点左子树进行中序遍历
2.访问根节点
3.对根节点的右子树进行中序遍历

  1. const bt = {
  2.     val:1,
  3.   left:{
  4.       val:2,
  5.     left:{
  6.         val:4,
  7.       left:null,
  8.       right:null
  9.     },
  10.     right:{
  11.       val:5,
  12.       left:null,
  13.       right:null
  14.     }  
  15.   },
  16.   right:{
  17.       val:3,
  18.     left:{
  19.         val:6,
  20.       left:null,
  21.       right:null
  22.     },
  23.     right:{
  24.       val:7,
  25.       left:null,
  26.       right:null
  27.     }  
  28.   }
  29. }
  31. const postorder = (root)=>{
  32.     if(!root){ return }
  33.   postorder(root.left);
  34.   postorder(root.right);
  35.   console.log(root.val);
  37. }
  38. postorder(bt)

二叉树最大深度-104.

（深度优先遍历）
1.求最大深度，考虑使用深度优先遍历
2.深度优先遍历过程中，记录每个节点所在的层级，找出最大的层级即可。

  1. const maxDepth = function(root){
  2.     let res = 0;
  3.   const defs = (n,l)=>{
  4.     if(!n){ return; };
  5.     if(!n.left && !n.right){
  6.       res = Math.max(res,l)
  7.     }
  8.     defs(n.left,l+1);
  9.     defs(n.right,l+1);
  10. }
  11.   defs(root,1);
  12.   return res
  13. }

二叉树最小深度-111.

（广度优先遍历）
1.广度优先遍历整个树，并且记录每个节点的层级
2.遇到叶子节点，返回层级节点，停止遍历

  1. const minDepth = function(root){
  2.     if(!root){return 0;}
  3.   const q = [[root,l]];
  4.   while(q.length){
  5.       const [n,l] = q.shift();
  6.     if(!n.left && !n.right){
  7.         return l
  8.     }
  9.     if(n.left){ q.push([n.left,l+1]) };
  10.     if(n.right){ q.push([n.right,l+1]) };
  11.   }
  12. }

二叉树层序遍历-102.

（广度优先遍历）

  1. const minDepth = function(root){
  2.     if(!root){return 0;}
  3.   const q = [[root,l]];
  4.   while(q.length){
  5.       const [n,l] = q.shift();
  6.     if(!n.left && !n.right){
  7.         return l
  8.     }
  9.     if(n.left){ q.push([n.left,l+1]) };
  10.     if(n.right){ q.push([n.right,l+1]) };
  11.   }
  12. }

路径总和-112.

(深度优先遍历)

  2. const hasPathSum = ()=>{
  3.   if(!root){
  4.       return false
  5.   }
  6.   let res = false
  8. }