遍历

前/中/后遍历

递归版本

//中序
var inorderTraversal = function(root) {
    let res = [];
    let inorder = (root) => {
        if (!root) return;
        inorder(root.left);
        res.push(root.val);//前中遍历仅需改变这行代码的顺序
        inorder(root.right);
    }
    inorder(root);
    return res;
};

迭代版本

可以先写中序遍历，然后前中遍历仅需改变两行代码的顺序

//中序遍历
var inorderTraversal = function(root) {
    //左中右 在栈中右左中
    let queue = [];
    let result= []
    if (root) {
      queue.push(root);
    }
    while (queue.length>0) {
      const node = queue.pop();
      if (!node) {
        const value = queue.pop();
        result.push(value.val)
      } else { 
        if (node.right) {
          queue.push(node.right);
        }
        queue.push(node);//
        queue.push(null);//前中遍历仅需改变这两行代码的顺序
        if (node.left) {
          queue.push(node.left);
        }
      }
    }
    return result;
};

层序遍历

层序遍历就是广度优先搜索遍历
使用层序遍历可以解决

111.二叉树的最小深度

//层序遍历
var levelOrder = function(root) {
 if(!root) return []
 let result=[];
 let queue=[root];
 while(queue.length>0){
     const length=queue.length;
     let nextLevel=[]
     for(let i =0;i<length;i++){
       const current=queue.shift();
       nextLevel.push(current.val)
       if(current.left) {
         queue.push(current.left);
       }
       if(current.right){
         queue.push(current.right);
       } 
     }
     result.push(nextLevel)
 }
 return result;
};

翻转二叉树

//自己写的
//前序遍历
var invertTree = function(root) {
 if(!root) return root;
 const left=root.left;
 root.left=root.right;
 root.right=left;
 invertTree(root.left)
 invertTree(root.right)
 return root;
};

//优化 
var invertTree = function(root) {
  if (!root) return null
  const tmp = root.left
  root.left = invertTree(root.right)
  root.right = invertTree(tmp)
  return root
};

平衡二叉树

树的高度和深度的区别
后序遍历

var isBalanced = function(root) {
function getTreeHeight(root){
  //后序遍历，从叶子节点开始计算高度，得到左右节点的高度差
  if(!root) return 0;
  const leftHeight=getTreeHeight(root.left);
  if(leftHeight===-1) return -1;
  const rightHeight=getTreeHeight(root.right);
  if(rightHeight===-1) return -1;
  if(Math.abs(leftHeight-rightHeight)>1) return -1;
  else return 1+Math.max(leftHeight,rightHeight); 
}
return !(getTreeHeight(root) === -1);
};

二叉树的直径

后序遍历

var diameterOfBinaryTree = function(root) {
let res=0;
dfs(root);
function dfs(node){
  if(!node) return 0;
  let left=dfs(node.left);
  let right=dfs(node.right);
  res=Math.max(res,left+right);
  return Math.max(left,right)+1;
}
return res;
};

236. 二叉树的最近公共祖先

用后序遍历先遍历到两个子节点再遍历到中间节点

var lowestCommonAncestor = function(root, p, q) {
 if(root===p || root===q || root===null) return root; //节点唯一，所以不会有重复q/p
  const left = lowestCommonAncestor(root.left,p,q)
  const right = lowestCommonAncestor(root.right,p,q)
  if(left && right) return root;
  if(!left && right) return right;
  if(left && !right) return left;
  return null;
};

235. 二叉搜索树的最近公共祖先

var lowestCommonAncestor = function(root, p, q) {
  //二叉搜索树，公共祖先在[p,q]之间
  if(root.val>p.val && root.val >q.val){
      return lowestCommonAncestor(root.left,p,q)
  }else if(root.val<p.val && root.val <q.val){
      return lowestCommonAncestor(root.right,p,q)
  }else return root;
};

回溯

<a name="CKTY9"></a>
## 112. 路径总和
```javascript
var hasPathSum = function(root, targetSum) {
 //回溯
     if(!root) return false;
     //注意要到叶子节点
     if(!root.left && !root.right && targetSum===root.val) return true
     //利用targetSum-root.val后撤
     return hasPathSum(root.left,targetSum-root.val) || hasPathSum(root.right,targetSum-root.val)
};

113.路径总和 II

var pathSum = function(root, targetSum) {
  let pathResult=[],pathArray=[] //需要保存路径
  function getTargetPath(root, targetSum){
    if(!root) return;
    pathArray.push(root.val)
    if(!root.left && !root.right && targetSum===root.val){
        pathResult.push([...pathArray]);
        return
    }
    if(root.left){
        getTargetPath(root.left,targetSum-root.val)
        pathArray.pop() //后撤
    }
    if(root.right){
        getTargetPath(root.right,targetSum-root.val)
        pathArray.pop()
    }
  }
  getTargetPath(root, targetSum)
  return pathResult;
};

搜索二叉树

二叉搜索树是一个有序树：

若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
它的左、右子树也分别为二叉搜索树

二叉搜索树中序遍历是一个递增序列，很重要的一点

98. 验证二叉搜索树

陷阱1

不能单纯的比较左节点小于中间节点，右节点大于中间节点就完事了。
我们要比较的是 左子树所有节点小于中间节点，右子树所有节点大于中间节点。

//方法一：因为二叉搜索树 中序遍历是一个递增序列。所以额外空间一个数组记录中序遍历结果
var isValidBST = function(root) { 
 let path=[] 
 function tranverse(root){//中序遍历
    if(!root) return;
    tranverse(root.left)
    path.push(root.val);
    tranverse(root.right)
 }
 tranverse(root)
 for(let i=1;i<path.length;i++){
     if(path[i]<=path[i-1]) return false;
 }
 return true;
};
//方法二：也可以不用额外空间，递归遍历时利用pre记录上一个数字进行比较
var isValidBST = function(root) { 
 let pre=-Infinity
 function tranverse(root){
    if(!root) return true;
    const left=tranverse(root.left)
    if(root.val>pre) pre=root.val
    else return false;
    const right=tranverse(root.right)
    return left && right
 }
 return tranverse(root)
};
//方法三： 不用递归，用迭代
var isValidBST = function (root) {
  let path = [];
  let pre = -Infinity;
  path.push(root);
  path.push(null);
  while (path.length > 0) {
    let node = path.pop();
    if (node) {
      if (node.val > pre) pre = node.val;
      else return false;
    } else {
      node = path.pop();
      if (node.right) {
        path.push(node.right);
        path.push(null);
      }
      path.push(node);
      if (node.left) {
        if (node.left) path.push(node.left);
        path.push(null);
      }
    }
  }
  return true;
};

108. 将有序数组转换为二叉搜索树

因为是有序数组，所以选取哪个为根节点都可以形成二叉搜索树，不过要求是高度平衡，所以要选取中间的为根节点。

var sortedArrayToBST = function(nums) {
    function traversal(nums,left,right){
        if (left > right) return null
        let mid=left + Math.ceil(((right - left) / 2));
      //也可以是let mid=left + Math.floor(((right - left) / 2)); 基准不同，但必须在中间
        let root=new TreeNode(nums[mid])
        root.left = traversal(nums, left, mid - 1);
        root.right = traversal(nums, mid + 1, right);
        return root
    }
    let root=traversal(nums, 0, nums.length - 1);
    return root;
};

算法

二叉树

遍历