1、二叉树遍历

  • 前序遍历(根—>左—>右)

    1. function perTreval(root){
    2.   if(!root) return [];
    3.   let res = [];
    4.   res.push(root.val)
    5.   res = res.concat(perTreval(root.left))
    6.   res = res.concat(perTreval(root.right))
    7.   return res;
    8. }

  • 中序遍历(左—>根—>右)

    1. function centerTreval(root){
    2.   if(!root) return [];
    3.   let res = [];
    4.   res = res.concat(centerTreval(root.left))
    5.   res.push(root.val)
    6.   res = res.concat(centerTreval(root.right))
    7.   return res;
    8. }

  • 后续遍历(左—>右—>根)

    1. function endTreval(root){
    2.   if(!root) return [];
    3.   let res = [];
    4.   res = res.concat(endTreval(root.left))
    5.   res = res.concat(endTreval(root.right))
    6.   res.push(root.val)
    7.   return res;
    8. }

2、N叉树遍历

  • 后续遍历 ```javascript var postorder = function(root) {

    if(!root) return []; let res = []; for(let i =0;i<root.children.length;i++){

    1.   res = res.concat(postorder(root.children[i]))

    } res.push(root.val) return res;

};

  2. - 前序遍历
  3. ```javascript
  4. var preorder = function(root) {
  5.     if(!root) return [];
  6.     let res = [];
  7.     res.push(root.val)
  8.     for(let i =0;i<root.children.length;i++){
  9.         res = res.concat(preorder(root.children[i]))
  10.     }
  11.     return res;
  13. };

  • 前序遍历和中序遍历结果，反向推导二叉树 ```javascript var buildTree = function(preorder, inorder) {

    if(preorder.length === 0 && inorder.length === 0){

    1.   return null

    } let root = {} root.val = preorder[0] let rootIndexOrder = inorder.indexOf(root.val)

    let leftTreeInOrder = inorder.slice(0,rootIndexOrder) let leftTreePreOrder = preorder.slice(1,leftTreeInOrder.length+1) root.left = buildTree(leftTreePreOrder,leftTreeInOrder)

    let rightTreeInOrder = inorder.slice(rootIndexOrder+1) let rightTreePreOrder = preorder.slice(rootIndexOrder+1)//右侧在pre和in中的位置一致 root.right = buildTree(rightTreePreOrder,rightTreeInOrder)

    return root;

}; ```