分类刷算法题（五）二叉树

今日来刷二叉树，咱们只做一些比较经典面试常考的二叉树标题，不去纠结难题

关于最基本的前序，中序，后序遍历我之前现已写过一篇关于遍历，递归的解法啦，如同也是榜首篇文章，就不在这儿赘述了,有兴趣的可以看看，横竖我自己复习都是看这儿来哈哈

二叉树的前序，中序，后序遍历【js实现】 – ()

一、二叉树经典标题

104. 二叉树的最大深度 – 力扣（LeetCode）
难度：简略
这个太经典啦，可是代码数量也很少，送分题好嘛
思路：
- 使用递归，每次回来左右子树深度的最大值+1(它本身）
- 递归最终便是回到根节点，回来即可
我把每一步都写出来了，其实整不明白的就可以看着代码，然后自己画图顺一下进程，就很明白了

var maxDepth = function(root) {
    if(root == null) return 0;
    //左子树的深度
    let left = maxDepth(root.left);
    //右子树的深度
    let right = maxDepth(root.right);
    //加上它本身
    let res = Math.max(left,right) +1;
    //回来成果
    return res
};

226. 翻转二叉树 – 力扣（LeetCode）
难度：简略
这个题跟上面的题其实差不多的，只要你搞懂了是怎样去递归，然后改一改代码就好了
这道题解题思路就十分明确了：以递归的方法，遍历树中的每一个结点，并将每一个结点的左右孩子进行交流

var invertTree = function(root) {
    if(!root) return null;
    //交流常用写法，用temp变量暂存
    let temp = root.left;
    root.left = root.right;
    root.right = temp;
    invertTree(root.left);
    invertTree(root.right);
   return root
};

101. 对称二叉树 – 力扣（LeetCode）
难度：简略
这道题跟上面那一道记得要区分好；首要咱们要搞清楚，究竟是怎样样的对称，和翻转的差异是什么
- 左右子树的根节点是否持平
- 左右子树是否镜像持平
思路：
- 以根节点作为起点
- 比较root1的左节点和root2的右节点
- 比较root1的右节点和root2的左节点
- 持平回来true，不等回来false

var isSymmetric = function(root){
    return isMirror(root,root)
};
const isMirror = function(root1, root2) {
    //一起为空的时分肯等是对称的
    if(!root1 && !root2) return true
    //这儿只剩下两种状况，要么root1为空，要么root2为空，那么肯等不对称
    if(!root1 || !root2) return false
    //比较节点的值
    if(root1.val != root2.val) return false
    //比较root1的左节点和root2的右节点 比较root1的右节点和root2的左节点
    return isMirror(root1.left, root2.right) && isMirror(root1.right, root2.left)
}

236. 二叉树的最近公共先人 – 力扣（LeetCode）
难度：中等
不要被难度中等吓到，它依旧是很经典的标题，咱们也依旧上咱们的递归大法，考虑每一个节点需求做什么操作即可
咱们分成三种状况
- p和q分别在根节点两边，那么最近公共先人便是根节点
- p和q都在左侧，则最先公共节点在左侧
- p和q都在右侧，则最先公共节点在右侧
思路：
- 假如树为空树或许p,q中任一节点为根节点，那么p,q的最近公共节点为根节点
- 假如树不为空且p,q为非根节点，则递归遍历左右子树，获取左右子树的最近公共先人
- 咱们由上面三种状况分别进行判别
  - 若left==null则阐明p,q都不在左子树，那么回来右子树成果
  - 若right==null则阐明p,q都不在右子树，那么回来左子树成果
  - 若左面不为空，右边不为空，则阐明该节点为他们的最近公共节点(由于咱们是递归实现的，那么榜首个找到的公共节点一定为他们最近公共节点)，那么回来该节点即可

var lowestCommonAncestor = function(root, p, q) {
    //树为空，p,q在根节点上的状况全都直接回来根节点
    if(!root || 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; //阐明p,q都不在左子树，那么回来右子树成果
    if(right == null ) return left;//阐明p,q都不在右子树，那么回来左子树成果
    return root ;//阐明p,q在根节点的两边，回来根节点
};

以上的题感觉都是很常见的经典题了，最好便是掌握好每一道题的思路，特别是作为基础的前序后序中序算法，在觉得递归难以了解的时分可以尝试画图辅佐了解；当然也可以去LeetCode找找有没有更亮点的做法

二、二叉查找树

首要咱们先了解一下什么是二叉查找树
二叉查找树也叫排序二叉树，二叉查找树，简称BST
二叉查找树指的是一颗空树或许其左子树上的一切节点的数据域都小于等于根节点的数据域，右子树一切结点的数据域都大于等于根节点的数据域
先来一道题稳固一下界说
98. 验证二叉查找树 – 力扣（LeetCode）
难度：中等
咱们上面说了两种状况，那么就直接剖析这两种状况
- 空树：直接回来true
- 非空树：需求递归地对非空树中的左右子树进行遍历，检验每棵子树中是否都满意左 < 根 < 右这样的关系

var isValidBST = function(root) {
    //初始化最大值和最小值
    return dfs(root, -Infinity, Infinity)
};
const dfs = function(root,min,max) {
    //满意空树条件，直接回来true即可
    if(!root) return true;
    //假如该右节点不符合右孩子不大于，或许左孩子不小于根节点，则不合法
    if(root.val <= min || root.val >= max) return false
    //每颗子树都要满意
    return dfs(root.left, min, root.val) && dfs(root.right, root.val, max);
}

700. 二叉查找树中的查找 – 力扣（LeetCode）
难度：简略
做完上面基础二叉树的经典题，你看到这道题应该就能自己写出思路了

var searchBST = function(root, val) {
    if(!root) return null;
    if(root.val == val) return root;
    const left = searchBST(root.left, val);
    const right = searchBST(root.right, val);
    return left || right;
};

做完你一想，假如这样的做法就能处理，那为什么要阐明是二叉查找树，是不是有更好的做法呢，如何使用起查找二叉树左小右大的特性
假如结点现已比方针值小了其实咱们就可以不用再递归其左子树了，
相同，假如结点现已比方针值大了，咱们就不用再递归其右子树了
所以咱们给递归加上判别即可
那么查找的节点为空的时分就阐明该树找不到方针节点

var searchBST = function(root, val) {
    if(!root) return null; //查找失败，直接回来
    //节点数值现已比方针数值大了，那么就只需求去查找左子树
    if(root.val > val) return searchBST(root.left, val); 
    //节点数值现已比方针数值小了，那么久只需求去查找右子树
    if(root.val < val) return searchBST(root.right, val);
    return root
};

701. 二叉查找树中的刺进操作 – 力扣（LeetCode）
难度：中等
虽然难度变成了中等，然后代码思维跟上一道题基本是一样的，回忆一下上一道题空节点的方位刚好就可以放入方针节点
所以只需求从根结点开始，把咱们期望刺进的数据值和每一个结点作比较。若大于当时结点，则向右子树探究；若小于当时结点，则向左子树探究。最终找到的那个空位，便是它合理的栖身之所

var insertIntoBST = function(root, val) {
    if(!root) {
    //刺进节点的栖身之地
        root = new TreeNode(val) 
        return root;
    }
    if(root.val > val) root.left = insertIntoBST(root.left, val);
    if(root.val < val ) root.right = insertIntoBST(root.right,val);
    return root
};

450. 删去二叉查找树中的节点 – 力扣（LeetCode）
难度：中等
这道题是基于榜首道题的扩展，咱们要删去节点，首要就要先找到该节点
- 假如找不到，则直接回来
- 假如找到后，他没有左右子树则直接删去即可
- 假如找到后，他只有一个非空子节点，那么直接让该子节点顶替他方位即可
- 假如找到后，他两个子节点都非空，那咱们为了不损坏BST的特性，只能去其左子树找到左子树的最大值替掉他，或许去其右子树找到最小的替调他（！所以有一些答案不仅有）

思路清晰之后，咱们只需求一步一步实现即可

首要先找到该节点

var deleteNode = function(root, key) {
    if(!root) return root;
    if(root.val == key) {
        //找到结点，等会来找删去操作
        console.log('我找到你啦', root.val); //我找到你啦，对应key值
        return root
    }
    if(root.val > key) root.left = deleteNode(root.left, key);
    if(root.val < key) root.right = deleteNode(root.right, key);
    return root
};

没有左右子树,直接删去

 if(!root.left && !root.right) {
        root = null
    }

只有一个非空节点

if(!root.left || !root.right) {
        root = root.left ? root.left: root.right;
 }

两个节点都非空，咱们先采取去其右子树找到最小的

  const mid = getMin(root.right); //找到右子树最小节点
  root.right = deleteNode(root.right, mid.val); //删去该结点
  mid.left = root.left; //让最小节点去替换root节点
  mid.right = root.right;
  root = mid;
  //找到最小节点
  const getMin = function(node) {
  //只需求找其右子树的左子树到最下面
    while(node.left != null) {
       node = node.left;
    }
    return node
}

一样的思路，咱们还可以选用去左子树找其最大的数

 const maxNode = getMax(root.left);
        root.left = deleteNode(root.left, maxNode.val);
        maxNode.left = root.left;
        maxNode.right = root.right;
        root = maxNode;
 const getMax = function(node) {
    while(node.right != null) {
       node = node.right;
    }
    return node
}

把每一步的代码合起来便是最终代码啦，这道题首要便是你需求先考虑好可能会出现什么状况，然后想好每一种状况是什么样的需求什么的处理，然后便是概括收拾优化代码了（这儿选用的是去左子树找最大的数）

var deleteNode = function(root, key) {
    if(!root) return root;
    if(root.val == key) {
        if(!root.left && !root.right) {
            root = null
        }else if(!root.left || !root.right) {
            root = root.left ? root.left: root.right;
        }else {
            const maxNode = getMax(root.left);
            root.left = deleteNode(root.left, maxNode.val);
            maxNode.left = root.left;
            maxNode.right = root.right;
            root = maxNode;
        }
        return root
    }
    if(root.val > key) root.left = deleteNode(root.left, key);
    if(root.val < key) root.right = deleteNode(root.right, key);
    return root
};
const getMax = function(node) {
    while(node.right != null) {
       node = node.right;
    }
    return node
}

关于二叉查找树，咱们只要可以掌握好它的约束条件和特性，就足以应对大部分的考题还可以做一下下面题稳固一下，难度都是简略

938. 二叉查找树的范围和 – 力扣（LeetCode）

783. 二叉查找树节点最小间隔 – 力扣（LeetCode）

530. 二叉查找树的最小肯定差 – 力扣（LeetCode）

501. 二叉查找树中的众数 – 力扣（LeetCode）

继续闯关平衡二叉树

三、平衡二叉树

平衡二叉树指的是任意结点的左右子树高度差肯定值都不大于1的二叉查找树
直接上题稳固一下界说
110. 平衡二叉树 – 力扣（LeetCode）
难度：简略
需求满意三个条件
- 每个节点左子树为平衡二叉树
- 每个节点右子树也为平衡二叉树
- 每个节点的的左子树和右子树的高度差肯定值不超越1
  - 求肯定值使用Math.abs()
  - 高度可以直接使用咱们前面做过的求深度算法，照搬便是了

var isBalanced = function(root) {
  if(!root) return true; //空树是平衡二叉树也是查找二叉树，直接回来true即可
  //递归查找三个条件
  return isBalanced(root.left) && isBalanced(root.right) && Math.abs(maxDepth(root.left) - maxDepth(root.right)) <=1
};
const maxDepth = function(root) {
    if(!root) return 0;
    return Math.max(maxDepth(root.left), maxDepth(root.right))+1
}

108. 将有序数组转换为二叉查找树 – 力扣（LeetCode）
难度：简略
这道题看标题是二叉查找树相关，可是详细看你会发现他要求的是转为高度平衡二叉树，也便是平衡二叉树啦
这道题还触及了一个特性：二叉查找树的中序遍历序列是有序的（由于左小右大），刚好跟咱们标题给的有序数组对应，所以有序数组的中心数字应该为树的根节点，那么思路就很显着了
咱们先找到数组中心数字，创立一个新节点
- 左子树为该数组中心数字左面的数组进入递归
- 右子树为该数组中心数组右边的数组进入递归
- 假如数组为空的时分就回来null

var sortedArrayToBST = function(nums) {
    //数组为空的时分回来空
    if(!nums.length) return null
    //找到中心结点
    const middle = Math.floor(nums.length/2);
    //new一个新节点
    const root = new TreeNode(nums[middle]);
    //选用slice以milddle为分割点去分割nums数组
    root.left = sortedArrayToBST(nums.slice(0,middle));
    root.right = sortedArrayToBST(nums.slice(middle+1));
    return root
};

四、其他题（看到就写系列）

116. 填充每个节点的下一个右侧节点指针 – 力扣（LeetCode）
难度：中等
做过上面的题后你看到这道题心里想，嘿嘿，容易！改改代码就行

var connect = function(root) {
    if(!root || !root.left) return null;
    root.left.next = root.right;
    connect(root.left);
    connect(root.right);
    return root
};

做完一看，不对，如同5和6没有衔接起来，你得到的是这样的
细心一想，咱们这种解法如同不能处理不同父节点的衔接，那么咱们可以尝试着自己去界说需求衔接的节点,以上图为例
- 4和5，6和7为同一父节点的应该相连
- 5和6为父节点为兄弟节点的应该相连

var connect = function(root) {
    if(!root) return null;
    traverse(root.left, root.right);
    return root
};
const traverse = function(root1, root2) {
    if(!root1 || !root2) return;
    root1.next = root2;
    //同一父节点
    traverse(root1.left,root1.right);
    traverse(root2.left,root2.right);
    //跨越父节点
    traverse(root1.right,root2.left);
}

还有其他算法题也可以看看，期望看完可以协助到你

分类刷算法题（一）链表 | 前端er – ()

分类刷算法题（二）栈和行列 | 前端er – ()

分类刷算法题（三）数组操作 | 前端er – ()

分类刷算法题（四）二分查找 | 前端er – ()

分类刷算法题（五）二叉树 | 前端er

一、二叉树经典标题

二、二叉查找树

三、平衡二叉树

四、其他题（看到就写系列）

作者信息

分类刷算法题 （五） 二叉树 | 前端er

一、二叉树经典标题

二、二叉查找树

三、平衡二叉树

四、其他题（看到就写系列）

相关文章

快到 35 的”大龄”程序员

GitHub 热点速览 Vol.16：化身蒙娜丽莎和乔布斯对话

如何以无服务器方式运行 Go 应用程序

NR – PBCH 211与DMRS以及PointA

作者信息

分类刷算法题（五）二叉树 | 前端er