• 递归
  • 遍历：写树相关的算法，简单说就是，先搞清楚当前 root 节点「该做什么」以及「什么时候做」，然后根据函数定义递归调用子节点，递归调用会让孩子节点做相同的事情。

所谓「该做什么」就是让你想清楚写什么代码能够实现题目想要的效果，所谓「什么时候做」，就是让你思考这段代码到底应该写在前序、中序还是后序遍历的代码位置上。

二叉树

理论基础

二叉树理论基础
二叉树类型：满二叉树、完全二叉树、二叉搜索树、平衡二叉树AVL
存贮：链式、顺序（数组）
遍历：深度（先中后）、广度（层次）

遍历

先中后序遍历

很多经典算法，回溯、动归、分治算法，其实都是树的问题，而树的问题就永远逃不开树的递归遍历框架这几行破代码：

  1. /* 二叉树遍历框架 */
  2. function traverse(TreeNode root) {
  3.     // 前序遍历
  4.     traverse(root.left)
  5.     // 中序遍历
  6.     traverse(root.right)
  7.     // 后序遍历
  8. }

image.png
先序：1 2 4 6 7 8 3 5 根左右
中序：4 7 6 8 2 1 3 5 左根右
后序：7 8 6 4 2 5 3 1 左右根

144. 二叉树的前序遍历

参考
递归

var preorderTraversal = function(root) {
    var res  = [];
    if(root == null) return res
    traversal(root,res)
    return res

};


function traversal(node, res) {
    res.push(node.val);
    node.left && traversal(node.left, res);
    node.right && traversal(node.right, res);
}

迭代

前序遍历:

// 入栈 右 -> 左
// 出栈 中 -> 左 -> 右
var preorderTraversal = function(root, res = []) {
    if(!root) return res;
    const stack = [root];
    let cur = null;
    while(stack.length) {
        cur = stack.pop();
        res.push(cur.val);
        cur.right && stack.push(cur.right);
        cur.left && stack.push(cur.left);
    }
    return res;
};

中序遍历:

// 入栈 左 -> 右
// 出栈 左 -> 中 -> 右

var inorderTraversal = function(root, res = []) {
    const stack = [];
    let cur = root;
    while(stack.length || cur) {
        if(cur) {
            stack.push(cur);
            // 左
            cur = cur.left;
        } else {
            // --> 弹出 中
            cur = stack.pop();
            res.push(cur.val); 
            // 右
            cur = cur.right;
        }
    };
    return res;
};

后序遍历:

// 入栈 左 -> 右
// 出栈 中 -> 右 -> 左 结果翻转

var postorderTraversal = function(root, res = []) {
    if (!root) return res;
    const stack = [root];
    let cur = null;
    do {
        cur = stack.pop();
        res.push(cur.val);
        cur.left && stack.push(cur.left);
        cur.right && stack.push(cur.right);
    } while(stack.length);
    return res.reverse();
};

94. 二叉树的中序遍历

145. 二叉树的后序遍历

589. N 叉树的前序遍历

const preorder = function(root) {
  const arr = []
  traverse(root, arr)
  return arr
};
function traverse(node, arr) {
  if(node === null) return
  arr.push(node.val)
  for(let i = 0; i < node.children.length; i++) {
    traverse(node.children[i], arr)
  }
}

590. N叉树后序遍历

层次遍历

层序遍历一个二叉树。就是从左到右一层一层的去遍历二叉树。

需要借用一个辅助数据结构即队列来实现，队列先进先出，符合一层一层遍历的逻辑，而是用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。
而这种层序遍历方式就是图论中的广度优先遍历，只不过我们应用在二叉树上。

使用队列实现二叉树广度优先遍历，动画如下：
102二叉树的层序遍历动画
这样就实现了层序从左到右遍历二叉树。
image.png

/* 二叉树层次遍历框架 */

// 0. 声明队列
queue=[]
res = []

// 1. 将根节点加入队列
queue.push(root);

// 2. 遍历队列中每个节点
while(queue.length!==0) {
    cur = q.shift()
    q.pop();
    // 3. 记录当前节点值
    res.push(cur.val);
    // 4. 将左右孩子放入队列
    q.push(cur.eft);
    q.push(cur.right);
}

02.二叉树的层序遍历

给定二叉树: [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
返回其层次遍历结果：

[
  [3],
  [9,20],
  [15,7]
]

var levelOrder = function(root) {

  if(root === null || root.length === 0){
    return [];
  }

    let queue = [], result = []
    queue.push(root)

    while(queue.length !== 0) {

      let level = []  //保存每层结果
      let size = queue.length;//// 记录当前层级节点数
      for(let i = 0; i < size; i++) {
        var node = queue.shift()
        level.push(node.val)
         node.left && queue.push(node.left)
         node.right && queue.push(node.right)
      }
       //把每一层的结果放到结果数组
      result.push(level)
    }
    return result
};

107. 二叉树的层序遍历 II

image.png
相对于102.二叉树的层序遍历，就是最后把result数组反转一下就可以了。

var levelOrderBottom = function(root) {

    if(!root) return [];

    var queue = [];
    var res = [];

    queue.push(root);
    while(queue.length != 0){
        var size  = queue.length;
        var level = [];
        for(let i=0;i<size;i++){
            var node = queue.shift()
            level.push(node.val)

              node.left &&  queue.push(node.left)
              node.right && queue.push(node.right)
        }
        res.push(level);
    }
    return res.reverse();//数组反转
};

199.二叉树的右视图

image.png
思路：
层序遍历的时候，将每层的最后一个元素就放进result数组中，随后返回result就可以了。

var rightSideView = function(root) {

    if(!root) return [];

    var queue = [];
    var res = [];

    queue.push(root);
    while(queue.length != 0){
        var size  = queue.length;
        var level = [];
        for(let i=0;i<size;i++){
            var node = queue.shift()
            level.push(node.val)

            node.left && queue.push(node.left)
            node.right &&  queue.push(node.right)
        }
        res.push(level.pop()); //将每层的最后一个元素放到res中
    }
    return res;   
};

637. 二叉树的层平均值

image.png
思路：每一层的结果求平均值

var averageOfLevels = function(root) {
    if(root == null) return null;
    let queue = [];
    let res = [];
    queue.push(root);
    while(queue.length>0){
        let level = [];
        let size = queue.length;
        for(let i=0;i<size;i++){
            let node = queue.shift();
            level.push(node.val);
            node.left && queue.push(node.left)
            node.right &&  queue.push(node.right)
        }
        const average = level.reduce((prev, curr) => prev + curr )/level.length;
        res.push(average);
    }
    return res;
};

429. N 叉树的层序遍历

    //每一层可能有2个以上,所以不再使用node.left node.right
    let res=[],queue=[];
    queue.push(root);
    while(queue.length && root){
        //记录每一层节点个数还是和二叉树一致
        let size=queue.length;
        //存放每层节点 也和二叉树一致
        let level=[];
         for(let i=0;i<size;i++){
            let node = queue.shift();
            level.push(node.val);
             //这里不再是 ndoe.left node.right 而是循坏node.children
            for(let item of node.children){
               item && queue.push(item);
            }
        }
        res.push(level);
    }
    return res;

515.在每个树行中找最大值

104. 二叉树的最大深度

var maxDepth = function(root) {
    // 最大的深度就是二叉树的层数
    if (root === null) return 0;
    let queue = [root];
    let height = 0;
    while (queue.length) {
        let n = queue.length;
        height++;
        for (let i=0; i<n; i++) {
            let node = queue.shift();
            node.left && queue.push(node.left);
            node.right && queue.push(node.right);
        }
    }
    return height;
};


var maxdepth = function(root) {
    //使用递归的方法 递归三部曲
    //1. 确定递归函数的参数和返回值
    const getdepth=function(node){
    //2. 确定终止条件
        if(node===null){
            return 0;
        }
    //3. 确定单层逻辑
        let leftdepth=getdepth(node.left);
        let rightdepth=getdepth(node.right);
        let depth=1+math.max(leftdepth,rightdepth);
        return depth;
    }
    return getdepth(root);
};

111. 二叉树的最小深度


相对于 104.二叉树的最大深度 ，本题还也可以使用层序遍历的方式来解决，思路是一样的。
需要注意的是，只有当左右孩子都为空的时候，才说明遍历的最低点了。如果其中一个孩子为空则不是最低点

var minDepth = function(root) {
    if (root === null) return 0;
    let queue = [root];
    let deepth = 0;
    while (queue.length) {
        let n = queue.length;
        deepth++;
        for (let i=0; i<n; i++) {
            let node = queue.shift();
            // 如果左右节点都是null，则该节点深度最小
            if (node.left === null && node.right === null) {
                return deepth;
            }
            node.left && queue.push(node.left);;
            node.right && queue.push (node.right);
        }
    }
    return deepth;
};

559. N 叉树的最大深度

//递归
var maxDepth = function(root) {
    if(root === null) return 0;
    var max = 1;
    root.children.forEach((child)=>{
        var depth = maxDepth(child) + 1;
        if(depth>max){
            max = depth;
        }
    })
    return max;
};

//迭代
var maxDepth = function(root) {
    if(root == null) return 0;
    let max = 0;
    let queue = [];
    queue.push(root);
    while(queue.length){
        const size = queue.length;
        max++;
        for(let i=0; i< size; i++){
           let node = queue.shift();
            for(let item of node.children){
               item && queue.push(item);
            }
        }
    }
    return max;
};

222. 完全二叉树的节点个数

var countNodes = function(root) {
    if(root == null) return 0;
    let queue = [];
    queue.push(root);
    let count = 0;

    while(queue.length){
        const size = queue.length;
        let node = queue.shift();
        count ++;
        node.left && queue.push(node.left);
        node.right && queue.push(node.right);
    }
    return count;
};

116. 填充每个节点的下一个右侧节点指针

给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点
image.png
思路:
本题依然是层序遍历，只不过在单层遍历的时候记录一下本层的头部节点，然后在遍历的时候让前一个节点指向本节点就可以了

var connect = function(root) {
    if (root === null) return root;
    let queue = [root];
    while (queue.length) {
        let n = queue.length;
        for (let i=0; i<n; i++) {
            let node = queue.shift();
            if (i < n-1) {
                node.next = queue[0];
            }
            node.left && queue.push(node.left);
            node.right && queue.push(node.right);
        }
    }
    return root;
};

117. 填充每个节点的下一个右侧节点指针 II


递归+层次

226.翻转二叉树

image.png
思路：
1.递归
2.层次遍历

var invertTree = function(root) {
    if(root == null){
        return null;
    }
     /**** 前序遍历位置 ****/
    // root 节点需要交换它的左右子节点
    let tmp = root.left;
    root.left = root.right;
    root.right = tmp;

    // 让左右子节点继续翻转它们的子节点
    invertTree(root.left);
    invertTree(root.right);
    return root;
};

var invertTree = function(root) {
    //我们先定义节点交换函数
    const invertNode=function(root,left,right){
        let temp=left;
        left=right;
        right=temp;
        root.left=left;
        root.right=right;
    }
    //使用层序遍历
    let queue=[];
    if(root===null){
        return root;
    } 
    queue.push(root);
    while(queue.length){
        let length=queue.length;
        while(length--){
            let node=queue.shift();
            //节点处理逻辑
            invertNode(node,node.left,node.right);
            node.left&&queue.push(node.left);
            node.right&&queue.push(node.right);
        }
    }
    return root;
};

101. 对称二叉树

思路1:递归
思路2：迭代-队列、栈

var isSymmetric = function(root) {
  //迭代方法判断是否是对称二叉树
  //首先判断root是否为空
  if(root===null){
      return true;
  }
  let stack=[];
  stack.push(root.left);
  stack.push(root.right);
  while(stack.length){
      let rightNode=stack.pop();
      let leftNode=stack.pop();
      if(leftNode===null&&rightNode===null){
          continue;
      }
      if(leftNode===null||rightNode===null||leftNode.val!==rightNode.val){
          return false;
      }
      stack.push(leftNode.left);//左节点左孩子入队
      stack.push(rightNode.right);//右节点右孩子入队
      stack.push(leftNode.right);//左节点右孩子入队
      stack.push(rightNode.left);//右节点左孩子入队
  }
  return true;
};

100. 相同的树

var isSameTree = function(p, q) {
    if(p==null && q== null){
        return true;
    }
    if(p!=null && q!=null && p.val == q.val){
        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    }else {
        return false
    }
};

572. 另一棵树的子树


// 判断两个数是否相等
function isSameTree(s,t){
    if (s == null && t == null) return true;
    return  s && t 
            && s.val == t.val 
            && isSametree(s.left, t.left) 
            && isSametree(s.right, t.right);
}

var isSubtree = function(root, subRoot) {
    if (root == null && subRoot == null) return true;
    if (root == null && subRoot != null) return false;

    return isSametree(root, subRoot)
        || isSubtree(root.left, subRoot)
        || isSubtree(root.right,subRoot);
};

110. 平衡二叉树

var isBalanced = function(root) {
    if (!root) return true;

    if (Math.abs(depth(root.left)-depth(root.right))>1) return false; 

    return isBalanced(root.left) && isBalanced(root.right); 

    function depth(node){
        if (!node) return 0;
        var left = depth(node.left);
        var right = depth(node.right);
        return Math.max(left, right)+1;
    }

};

404. 左叶子之和

    3
   / \
  9  20
    /  \
   15   7

在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24
  1. 递归法：后序遍历 左右中
  2. 迭代法: 层次遍历

判断当前节点是不是左叶子是无法判断的，必须要通过节点的父节点来判断其左孩子是不是左叶子。

var sumOfLeftLeaves = function(root) {
   //采用层序遍历
   if(root===null){
       return null;
   }
   let queue = [];
   let sum = 0;
   queue.push(root);
   while(queue.length){
     let node = queue.shift();
     if(node.left!==null&&node.left.left===null&&node.left.right===null){
         sum+=node.left.val;
     }
     node.left&&queue.push(node.left);
     node.right&&queue.push(node.right);
   }
   return sum;
};

var sumOfLeftLeaves = function(root) {
    //采用后序遍历 递归遍历
    // 1. 确定递归函数参数
    const nodesSum = function(node){
        // 2. 确定终止条件
        if(node===null){
            return 0;
        }
        let leftValue = sumOfLeftLeaves(node.left);
        let rightValue = sumOfLeftLeaves(node.right);
        // 3. 单层递归逻辑
        let midValue = 0;
        if(node.left&&node.left.left===null&&node.left.right===null){
            midValue = node.left.val;
        }
        let sum = midValue + leftValue + rightValue;
        return sum;
    }
    return nodesSum(root);
};

513. 找树左下角的值

image.png

//如果找最左边的呢？可以使用前序遍历，这样才先优先左边搜索，然后记录深度最大的叶子节点，此时就是树的最后一行最左边的值。
var findBottomLeftValue = function(root) {
    //考虑层序遍历 记录最后一行的第一个节点
    let queue = [];
    if(root===null){
        return null;
    }
    queue.push(root);
    let resNode;
    while(queue.length){
        let length =  queue.length;
        for(let i=0; i<length; i++){
            let node = queue.shift();
            if(i===0){
                resNode = node.val;
            }
            node.left&&queue.push(node.left);
            node.right&&queue.push(node.right);
        }
    }
    return resNode;
};

var findBottomLeftValue = function(root) {
    //首先考虑递归遍历 前序遍历 找到最大深度的叶子节点即可
    let maxPath = 0,resNode = null;
    // 1. 确定递归函数的函数参数
    const dfsTree = function(node,curPath){
    // 2. 确定递归函数终止条件
        if(node.left===null&&node.right===null){
            if(curPath>maxPath){
            maxPath = curPath;
            resNode = node.val;
            }
            // return ;
        }
        node.left&&dfsTree(node.left,curPath+1);
        node.right&&dfsTree(node.right,curPath+1);
    }
    dfsTree(root,1);
    return resNode;
};

112. 路径总和

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum ，判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。
image.png

let haspathsum = function (root, targetsum) {
  // 递归法
  const traversal = (node, cnt) => {
    // 遇到叶子节点，并且计数为0
    if (cnt === 0 && !node.left && !node.right) return true;
    // 遇到叶子节点而没有找到合适的边(计数不为0)，直接返回
    if (!node.left && !node.right) return false;

    //  左（空节点不遍历）.遇到叶子节点返回true，则直接返回true
    if (node.left && traversal(node.left, cnt - node.left.val)) return true;
    //  右（空节点不遍历）  
    if (node.right && traversal(node.right, cnt - node.right.val)) return true;
    return false;
  };
  if (!root) return false;
  return traversal(root, targetsum - root.val);

  // 精简代码:
  // if (!root) return false;
  // if (!root.left && !root.right && targetsum === root.val) return true;
  // return haspathsum(root.left, targetsum - root.val) || haspathsum(root.right, targetsum - root.val);
};

257. 二叉树的所有路径

image.png
递归+前序遍历

var binaryTreePaths = function(root) {
   //递归遍历+递归三部曲
   let res=[];
   //1. 确定递归函数 函数参数
   const getPath=function(node,curPath){
    //2. 确定终止条件，到叶子节点就终止
       if(node.left===null&&node.right===null){
           curPath+=node.val;
           res.push(curPath);
           return ;
       }
       //3. 确定单层递归逻辑
       curPath+=node.val+'->';
       node.left&&getPath(node.left,curPath);
       node.right&&getPath(node.right,curPath);
   }
   getPath(root,'');
   return res;
};

113. 路径总和 II

image.png

let pathsum = function (root, targetsum) {
  // 递归法
  // 要遍历整个树找到所有路径，所以递归函数不需要返回值, 与112不同
  const res = [];
  const travelsal = (node, cnt, path) => {
    // 遇到了叶子节点且找到了和为sum的路径
    if (cnt === 0 && !node.left && !node.right) {
      res.push([...path]); // 不能写res.push(path), 要深拷贝
      return;
    }
    if (!node.left && !node.right) return; // 遇到叶子节点而没有找到合适的边，直接返回
    // 左 （空节点不遍历）
    if (node.left) {
      path.push(node.left.val);
      travelsal(node.left, cnt - node.left.val, path); // 递归
      path.pop(); // 回溯
    }
    // 右 （空节点不遍历）
    if (node.right) {
      path.push(node.right.val);
      travelsal(node.right, cnt - node.right.val, path); // 递归
      path.pop(); // 回溯
    }
    return;
  };
  if (!root) return res;
  travelsal(root, targetsum - root.val, [root.val]); // 把根节点放进路径
  return res;
};

106. 从中序与后序遍历序列构造二叉树

image.png
image.png

  • 第一步：如果数组大小为零的话，说明是空节点了。
  • 第二步：如果不为空，那么取后序数组最后一个元素作为节点元素。
  • 第三步：找到后序数组最后一个元素在中序数组的位置，作为切割点
  • 第四步：切割中序数组，切成中序左数组和中序右数组 （顺序别搞反了，一定是先切中序数组）
  • 第五步：切割后序数组，切成后序左数组和后序右数组
  • 第六步：递归处理左区间和右区间
var buildTree = function(inorder, postorder) {
    if (!postorder.length) return null

    let root = new TreeNode(postorder[postorder.length - 1])

    let index = inorder.findIndex(number => number === root.val)

    root.left = buildTree(inorder.slice(0, index), postorder.slice(0, index))
    root.right = buildTree(inorder.slice(index + 1, inorder.length), postorder.slice(index, postorder.length - 1))

    return root
};

105. 从前序与中序遍历序列构造二叉树

image.png
前序和中序可以唯一确定一颗二叉树。
后序和中序可以唯一确定一颗二叉树。
那么前序和后序可不可以唯一确定一颗二叉树呢？
前序和后序不能唯一确定一颗二叉树！，因为没有中序遍历无法确定左右部分，也就是无法分割。

var buildTree = function(preorder, inorder) {
    if(!preorder.length)
        return null;
    let root = new TreeNode(preorder[0]);
    let mid = inorder.findIndex((number) => number === root.val);
    root.left = buildTree(preorder.slice(1, mid + 1), inorder.slice(0, mid));
    root.right = buildTree(preorder.slice(mid + 1, preorder.length), inorder.slice(mid + 1, inorder.length));
    return root;
};

654. 最大二叉树

image.png

构造树一般采用的是前序遍历，因为先构造中间节点，然后递归构造左子树和右子树。

 var constructMaximumBinaryTree = function (nums) {
    const BuildTree = (arr, left, right) => {
        if (left > right)
            return null;
        let maxValue = -1;
        let maxIndex = -1;
        for (let i = left; i <= right; ++i) {
            if (arr[i] > maxValue) {
                maxValue = arr[i];
                maxIndex = i;
            }
        }
        let root = new TreeNode(maxValue);
        root.left = BuildTree(arr, left, maxIndex - 1);
        root.right = BuildTree(arr, maxIndex + 1, right);
        return root;
    }
    let root = BuildTree(nums, 0, nums.length - 1);
    return root;
};

617. 合并二叉树

image.png

var mergeTrees = function (root1, root2) {
    const preOrder = (root1, root2) => {
        if (!root1)
            return root2
        if (!root2)
            return root1;
        root1.val += root2.val;
        root1.left = preOrder(root1.left, root2.left);
        root1.right = preOrder(root1.right, root2.right);
        return root1;
    }
    return preOrder(root1, root2);
};

var mergeTrees = function(root1, root2) {
    if (root1 === null) return root2;
    if (root2 === null) return root1;

    let queue = [];
    queue.push(root1);
    queue.push(root2);
    while (queue.length) {
        let node1 = queue.shift();
        let node2 = queue.shift();;
        node1.val += node2.val;
        if (node1.left !== null && node2.left !== null) {
            queue.push(node1.left);
            queue.push(node2.left);
        }
        if (node1.right !== null && node2.right !== null) {
            queue.push(node1.right);
            queue.push(node2.right);
        }
        if (node1.left === null && node2.left !== null) {
            node1.left = node2.left;
        }
        if (node1.right === null && node2.right !== null) {
            node1.right = node2.right;
        } 
    }
    return root1;
};

BST

基本数据结构

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

image.png

左节点 < 根节点 < 右节点 中序遍历之后为二叉排序树
框架
image.png

class TreeNode {
  constructor(val, left, right) {
    this.val = val;
    this.left = left || null;
    this.right = right || null;
  }
  show() {
    console.log(this.val);
  }
}

class BinarySearchTree {
  constructor() {
    this.root = null;
  }
  //要插入节点，必须先找到插入的位置。
  //由于二叉搜索树的特殊性，待插入的节点也需要从根节点开始进行比较
  //小于根节点则与根节点左子树比较，反之则与右子树比较，直到左子树为空或右子树为空
  //比较的过程中要保存父节点的信息及待插入的位置是父节点的左子树还是右子树，才能插入到正确的位置
  insert(val) {
    let node = new TreeNode(val);
    if (this.root === null) {
      this.root = node;
      return;
    }
    let cur = this.root;
    let parent = null;
    while (cur) {
      parent = cur; // 记录每次cur的位置，以便插入子节点
      if (val < parent.val) {
        cur = cur.left;
        if (!cur) {
          parent.left = node;
          return;
        }
      } else {
        cur = cur.right;
        if (!cur) {
          parent.right = node;
          return;
        }
      }
    }
  }

  //BST最小值在最左子节点
  getMin() {
    if (this.root === null) return;
    var cur = this.root;
    while (cur) {
      if (!cur.left) {
        return cur;
      }
      cur = cur.left;
    }
  }
  //最大值在最右子节点
  getMax() {
    if (this.root === null) return;
    var cur = this.root;
    while (cur) {
      if (!cur.right) {
        return cur;
      }
      cur = cur.right;
    }
  }
  getDeep(node, deep) {
    deep = deep || 0;
    if (node == null) {
      return deep;
    }
    deep++;
    var dleft = this.getDeep(node.left, deep);
    var dright = this.getDeep(node.right, deep);
    return Math.max(dleft, dright);
  }
  //val是要找到对应数值的节点，root是根节点
  //循环实现
  // getNode(val,root) {
  //   if(root === null) return;
  //   var cur = root;
  //   while(cur){
  //     if(val === cur.val){
  //       return cur
  //     }else if(val<cur.val){
  //       cur =cur.left
  //     } else{
  //       cur =cur.right
  //     }
  //   }
  // },
  //递归
  getNode(val, node) {
    if (node === null) return;

    if (val === node.val) {
      return node;
    } else if (val < node.val) {
      return this.getNode(val, node.left);
    } else {
      return this.getNode(val, node.right);
    }
  }
  //先序遍历
  preOrder(node) {
    if (node) {
      node.show();
      this.preOrder(node.left);
      this.preOrder(node.right);
    }
  }
  //中序遍历
  middleOrder(node) {
    if (node) {
      this.middleOrder(node.left);
      node.show();
      this.middleOrder(node.right);
    }
  }
  // 后续遍历
  laterOrder(node) {
    if (node) {
      this.laterOrder(node.left);
      this.laterOrder(node.right);
      node.show();
    }
  }
}

var t = new BinarySearchTree();
t.insert(4);
t.insert(3);
t.insert(8);
t.insert(1);
t.insert(2);
t.insert(5);
t.insert(7);
t.insert(6);
t.insert(0);
console.log(t);
console.log(t.getMax());
console.log(t.getMin());
// console.log(t.getDeep(t.root, 0));
// console.log(t.getNode(5, t.root));
// t.middleOrder(t.root);
// t.laterOrder(t.root);

练习

剑指 Offer 54. 二叉搜索树的第k大节点

image.png
二叉树的中序遍历 右 - 根 - 左，放到一个数组中 再返回数组的第 k 大的数

var kthLargest = function(root, k) {
  let ans = [];

  function largest(node) {
    if (node === null) return ;

    largest(node.right);
    ans.push( node.val );
    largest(node.left);
  }
  largest(root);

  return ans[k - 1];
};


98. 验证二叉搜索树

要知道中序遍历下，输出的二叉搜索树节点的数值是有序序列。
有了这个特性，验证二叉搜索树，就相当于变成了判断一个序列是不是递增的了。

var isValidBST = function (root) {
    let arr = [];
    const buildArr = (root) => {
        if (root) {
            buildArr(root.left);
            arr.push(root.val);
            buildArr(root.right);
        }
    }
    buildArr(root);
    for (let i = 1; i < arr.length; ++i) {
        if (arr[i] <= arr[i - 1])
            return false;
    }
    return true;
};

530. 二叉搜索树的最小绝对差

image.png

var getMinimumDifference = function (root) {
    let arr = [];
    const buildArr = (root) => {
        if (root) {
            buildArr(root.left);
            arr.push(root.val);
            buildArr(root.right);
        }
    }
    buildArr(root);
    let diff = arr[arr.length - 1];
    for (let i = 1; i < arr.length; ++i) {
        if (diff > arr[i] - arr[i - 1])
            diff = arr[i] - arr[i - 1];
    }
    return diff;
};

501. 二叉搜索树中的众数

image.png

思路：
如果不是二叉搜索树，对树进行比遍历，用map统计频率，把统计的出来的出现频率（即map中的value）排个序

既然是搜索树，它中序遍历就是有序的。

var findMode = function(root) {
    // 使用递归中序遍历
    let map = new Map();
    // 1. 确定递归函数以及函数参数
    const traverTree = function(root) {
        // 2. 确定递归终止条件
        if(root === null) {
            return ;
        }
        traverTree(root.left);
         // 3. 单层递归逻辑
        map.set(root.val,map.has(root.val)?map.get(root.val)+1:1);
        traverTree(root.right);
    }
    traverTree(root);
    //上面把数据都存储到map
    //下面开始寻找map里面的
    // 定义一个最大出现次数的初始值为root.val的出现次数
    let maxCount = map.get(root.val);
    // 定义一个存放结果的数组res
    let res = [];
    for(let [key,value] of map) {
        // 如果当前值等于最大出现次数就直接在res增加该值
        if(value === maxCount) {
            res.push(key);
        }
        // 如果value的值大于原本的maxCount就清空res的所有值，因为找到了更大的
        if(value>maxCount) {
            res = [];
            maxCount = value;
            res.push(key);
        }
    }
    return res;
};

var findMode = function(root) {
    // 不使用额外空间，使用中序遍历,设置出现最大次数初始值为1
    let count = 0,maxCount = 1;
    let pre = root,res = [];
    // 1.确定递归函数及函数参数
    const travelTree = function(cur) {
        // 2. 确定递归终止条件
        if(cur === null) {
            return ;
        }
        travelTree(cur.left);
        // 3. 单层递归逻辑
        if(pre.val === cur.val) {
            count++;
        }else {
            count = 1;
        }
        pre = cur;
        if(count === maxCount) {
            res.push(cur.val);
        }
        if(count > maxCount) {
            res = [];
            maxCount = count;
            res.push(cur.val);
        }
        travelTree(cur.right);
    }
    travelTree(root);
    return res;
};

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

image.png
本题是二叉搜索树，二叉搜索树是有序的，那得好好利用一下这个特点。
在有序树里，如果判断一个节点的左子树里有p，右子树里有q呢？
其实只要从上到下遍历的时候，cur节点是数值在[p, q]区间中则说明该节点cur就是最近公共祖先了。

和二叉树：公共祖先问题不同，普通二叉树求最近公共祖先需要使用回溯，从底向上来查找，二叉搜索树就不用了，因为搜索树有序（相当于自带方向），那么只要从上向下遍历就可以了。

var lowestCommonAncestor = function(root, p, q) {
    // 使用迭代的方法
    while(root) {
        if(root.val>p.val&&root.val>q.val) {
            root = root.left;
        }else if(root.val<p.val&&root.val<q.val) {
            root = root.right;
        }else {
            return root;
        }

    }
    return null;
};

var lowestCommonAncestor = function(root, p, q) {
    // 使用递归的方法
    // 1. 使用给定的递归函数lowestCommonAncestor
    // 2. 确定递归终止条件
    if(root === null) {
        return root;
    }
    if(root.val>p.val&&root.val>q.val) {
        // 向左子树查询
        let left = lowestCommonAncestor(root.left,p,q);
        return left !== null&&left;
    }
    if(root.val<p.val&&root.val<q.val) {
        // 向右子树查询
        let right = lowestCommonAncestor(root.right,p,q);
        return right !== null&&right;
    }
    return root;
};

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

image.png
https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0236.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%9C%80%E8%BF%91%E5%85%AC%E5%85%B1%E7%A5%96%E5%85%88.md

遇到这个题目首先想的是要是能自底向上查找就好了，这样就可以找到公共祖先了。
那么二叉树如何可以自底向上查找呢？
回溯啊，二叉树回溯的过程就是从低到上。
后序遍历就是天然的回溯过程，最先处理的一定是叶子节点。
接下来就看如何判断一个节点是节点q和节点p的公共公共祖先呢。

如果找到一个节点，发现左子树出现结点p，右子树出现节点q，或者 左子树出现结点q，右子树出现节点p，那么该节点就是节点p和q的最近公共祖先。

image.png
image.png
图解：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/solution/236-er-cha-shu-de-zui-jin-gong-gong-zu-xian-hou-xu/

const lowestCommonAncestor = function(root, p, q) {
    if(root == null || root == p || root == q) return root
    const left = lowestCommonAncestor(root.left, p, q)
    const right = lowestCommonAncestor(root.right, p, q)
    if(left === null) return right
    if(right === null) return left
    return root
};

701. 二叉搜索树中的插入操作

image.png

var insertIntoBST = function(root, val) {
     const node = new TreeNode(val);
     if(root === null) return node;
     let cur = root;
     let parent = null;
     while(cur){
         parent = cur;
         if(cur.val<val){
             cur=cur.right;
            if(cur === null){
                parent.right = node
             }
         } else if(cur.val>val){
             cur = cur.left;
             if(cur === null){
                 parent.left = node
             }
         }
     }
     return root;
};

var insertIntoBST = function(root, val) {
     const setInOrder = (root, val) => {
        if (root === null) {
            let node = new TreeNode(val);
            return node;
        }
        if (root.val > val)
            root.left = setInOrder(root.left, val);
        else if (root.val < val)
            root.right = setInOrder(root.right, val);
        return root;
    }
    return setInOrder(root, val);

};

450. 删除二叉搜索树中的节点

image.png

  • 第一种情况：没找到删除的节点，遍历到空节点直接返回了
  • 找到删除的节点
    • 第二种情况：左右孩子都为空（叶子节点），直接删除节点， 返回NULL为根节点
    • 第三种情况：删除节点的左孩子为空，右孩子不为空，删除节点，右孩子补位，返回右孩子为根节点
    • 第四种情况：删除节点的右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点
    • 第五种情况：左右孩子节点都不为空，必须找到左子树中最大的那个节点，或者右子树中最小的那个节点来接替自己。我们以第二种方式讲解。

image.png

var deleteNode = function (root, key) {
    if(root == null) return null;
    if(root.val === key){
        //找到值进行删除
        //1.末端节点 左右子树为空 直接删除
        if(root.left === null && root.right === null){
            return null;
        }
        // 2. 只有一个非空节点 让孩子直接代替自己
        if (root.left == null) return root.right;
        if (root.right == null) return root.left;

        // 3.节点有两个子节点，必须找到左子树中最大的那个节点，或者右子树中最小的那个节点来接替自己。我们以第二种方式讲解。
        const minNode = getMin(root.right);
        root.val = minNode.val;
        root.right = deleteNode(root.right,minNode.val);

    } else if(root.val >key){
        //开始找左子树
        root.left = deleteNode(root.left,key);
    } else if(root.val < key){
        //开始找右子树
       root.right = deleteNode(root.right,key)
    }
    return root;
};

function getMin(node){
    while(node.left !== null) {
        node = node.left;
    }
    return node;
}

538. 把二叉搜索树转换为累加树

image.png

从树中可以看出累加的顺序是右中左，所以我们需要反中序遍历这个二叉树，然后顺序累加就可以了。

换一个角度来看，这就是一个有序数组[2, 5, 13]，求从后到前的累加数组，也就是[20, 18, 13]，是不是感觉这就简单了。

var convertBST = function(root) {
    let pre = 0;
    const ReverseInOrder = (cur) => {
        if(cur) {
            ReverseInOrder(cur.right);
            cur.val += pre;
            pre = cur.val;
            ReverseInOrder(cur.left);
        }
    }
    ReverseInOrder(root);
    return root;
};

var convertBST = function (root) {
    let pre = 0;
    let cur = root;
    let stack = [];
    while (cur !== null || stack.length !== 0) {
        while (cur !== null) {
            stack.push(cur);
            cur = cur.right;
        }
        cur = stack.pop();
        cur.val += pre;
        pre = cur.val;
        cur = cur.left;
    }
    return root;
};

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

image.png

本质就是寻找分割点，分割点作为当前节点，然后递归左区间和右区间。
分割点就是数组中间位置的节点。
那么为问题来了，如果数组长度为偶数，中间节点有两个，取哪一个？
取哪一个都可以，只不过构成了不同的平衡二叉搜索树。
例如：输入：[-10,-3,0,5,9]
如下两棵树，都是这个数组的平衡二叉搜索树：
image.png

var sortedArrayToBST = function (nums) {
    const buildTree = (Arr, left, right) => {
        if (left > right)
            return null;

        let mid = Math.floor(left + (right - left) / 2);

        let root = new TreeNode(Arr[mid]);
        root.left = buildTree(Arr, left, mid - 1);
        root.right = buildTree(Arr, mid + 1, right);
        return root;
    }
    return buildTree(nums, 0, nums.length - 1);
};