• Leetcode hot 100之二叉树

    目录

     (反)序列化二叉树（str<->tree）：前序

    前序遍历（迭代）/路径

    stack.length

    入栈：中右左

    出栈：中左右

    中序遍历（迭代）

    cur||stack.length

    后序遍历（迭代）

    和前序遍历不同：

    入栈：中左右

    出栈：中右左

    reverse出栈：左右中

    层序遍历（BFS）：可求树的深/高度

    找树左下角的值：最后一行的最左边的值

    判断完全二叉树

    queue.length

    flag = false; //是否遇到空节点

    判断平衡二叉树

    递归Math.max(getMaxDepth(root.left)+1,getMaxDepth(root.right)+1)

    判断对称二叉树

    递归deep(left.left, right.right) && deep(left.right, right.left)

    翻转/生成镜像二叉树

    递归交换左右

    两节点的最近公共祖先

    递归后序遍历

    构造二叉树

    从中序与前/后序遍历序列构造二叉树

    最大二叉树：二叉树的根是数组中的最大元素（递归定义）

    二叉搜索树：左<根<右（按中序遍历有序的树）

    删除二叉搜索树中的节点

    修剪二叉搜索树

    有序数组转换为平衡二叉搜索树

    left, right比arr.slice高效

    Math.floor(left + (right - left) / 2)

    最值、差值->有序数组的差值、最值

    二叉搜索树的最小绝对差

    二叉搜索树转换为累加树

     (反)序列化二叉树（str<->tree）：前序

    1. function TreeNode(x) {
    2.     this.val = x;
    3.     this.left = null;
    4.     this.right = null;
    5. }
    6. //反序列化二叉树：tree->str 把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串
    7. function Serialize(pRoot, arr = []) {
    8.     if (!pRoot) {
    9.         arr.push("#");
    10.         return arr;
    11.     } else {
    12.         arr.push(pRoot.val);//注意是val。而不是root
    13.         Serialize(pRoot.left, arr);
    14.         Serialize(pRoot.right, arr);
    15.     }
    16.     return arr;
    17. }
    18. //序列化二叉树：str->tree 根据字符串结果str，重构二叉树
    19. function Deserialize(s) {
    20.     //转换为数组
    21.     let arr = Array.isArray(s) ? s : s.split("");
    22.     //取出val
    23.     let a = arr.shift();
    24.     //构建二叉树结点
    25.     let node = null;
    26.     if (typeof a === "number") {
    27.         //还有可能等于#
    28.         node = new TreeNode(a);
    29.         node.left = Deserialize(arr);
    30.         node.right = Deserialize(arr);
    31.     }
    32.     return node;
    33. }
    34. module.exports = {
    35.     Serialize: Serialize,
    36.     Deserialize: Deserialize,
    37. };

     递归->栈

    1. //递归
    2. function recursion() {
    3.     let res;
    4.     res+=recursion(...);
    5.     return res;
    6. }
    7. //栈
    8. function iterative() {
    9.     let res;
    10.     const stack = [root]; 
    11.     while (stack.length > 0) {
    12.         const current = stack.pop(); 
    13.         res+=...
    14.         stack.push();
    15.     }
    16.     return res;
    17. }

    前序遍历（迭代）/路径

    stack.length

    入栈：中右左

    出栈：中左右

    1. /**
    2.  * Definition for a binary tree node.
    3.  * function TreeNode(val, left, right) {
    4.  *     this.val = (val===undefined ? 0 : val)
    5.  *     this.left = (left===undefined ? null : left)
    6.  *     this.right = (right===undefined ? null : right)
    7.  * }
    8.  */
    9. /**
    10.  * @param {TreeNode} root
    11.  * @return {number[]}
    12.  */
    13. var preorderTraversal = function(root) {
    14.     let stack=[]
    15.     let res = []
    16.     let cur = null;
    17.     if(!root) return res;
    18.     root&&stack.push(root)
    19.     while(stack.length){
    20.         cur = stack.pop()
    21.         res.push(cur.val)
    22.         cur.right&&stack.push(cur.right)
    23.         cur.left&&stack.push(cur.left)
    24.     }
    25.     return res
    26. };

    中序遍历（迭代）

    cur||stack.length

    指针的遍历来帮助访问节点，栈则用来处理节点上的元素

    1. /**
    2.  * Definition for a binary tree node.
    3.  * function TreeNode(val, left, right) {
    4.  *     this.val = (val===undefined ? 0 : val)
    5.  *     this.left = (left===undefined ? null : left)
    6.  *     this.right = (right===undefined ? null : right)
    7.  * }
    8.  */
    9. /**
    10.  * @param {TreeNode} root
    11.  * @return {number[]}
    12.  */
    13. var inorderTraversal = function(root) {
    14.     let stack = []
    15.     let res = []
    16.     let cur = root
    17.     while(cur||stack.length){
    18.         if(cur){
    19.             stack.push(cur)
    20.             cur = cur.left
    21.         } else {
    22.             cur = stack.pop()
    23.             res.push(cur.val)
    24.             cur = cur.right
    25.         }
    26.     }
    27.     return res
    28. };

    后序遍历（迭代）

    和前序遍历不同：

    入栈：中左右

    出栈：中右左

    reverse出栈：左右中

    1. /**
    2.  * Definition for a binary tree node.
    3.  * function TreeNode(val, left, right) {
    4.  *     this.val = (val===undefined ? 0 : val)
    5.  *     this.left = (left===undefined ? null : left)
    6.  *     this.right = (right===undefined ? null : right)
    7.  * }
    8.  */
    9. /**
    10.  * @param {TreeNode} root
    11.  * @return {number[]}
    12.  */
    13. var postorderTraversal = function(root) {
    14.     let stack = []
    15.     let res = []
    16.     let cur = root
    17.     if(!root) return res
    18.     stack.push(root)
    19.     while(stack.length){
    20.         cur = stack.pop()
    21.         res.push(cur.val)
    22.         cur.left&&stack.push(cur.left)
    23.         cur.right&&stack.push(cur.right)
    24.     }
    25.     return res.reverse()
    26.  
    27. };

    层序遍历（BFS）：可求树的深/高度

    树的层序遍历，相似 图的广度优先搜索

    1. 初始设置一个空队，根结点入队
    2. 队首结点出队，其左右孩子 依次 入队
    3. 若队空，说明 所有结点 已处理完，结束遍历；否则（2)
    1. /*
    2.  * function TreeNode(x) {
    3.  *   this.val = x;
    4.  *   this.left = null;
    5.  *   this.right = null;
    6.  * }
    7.  */
    8.  
    9. /**
    10.  *
    11.  * @param root TreeNode类
    12.  * @return int整型二维数组
    13.  */
    14. function levelOrder(root) {
    15.     // write code here
    16.     if (root == null) {
    17.         return [];
    18.     }
    19.  
    20.     const arr = [];
    21.     const queue = [];
    22.  
    23.     queue.push(root);
    24.  
    25.     while (queue.length) {
    26.         const preSize = queue.length;
    27.         const floor = [];//当前层
    28.         for (let i = 0; i < preSize; ++i) {
    29.             const v = queue.shift();
    30.             floor.push(v.val);
    31.             v.left&&queue.push(v.left);
    32.             v.right&&queue.push(v.right);
    33.         }
    34.         arr.push(floor);
    35.     }
    36.     return arr;//[[1],[2,3]]
    37. }
    38. module.exports = {
    39.     levelOrder: levelOrder,
    40. };

    找树左下角的值：最后一行的最左边的值

    判断完全二叉树

    queue.length

    flag = false; //是否遇到空节点

    完全二叉树：叶子节点只能出现在最下层和次下层，且最下层的叶子节点集中在树的左部。

    1. /*
    2.  * function TreeNode(x) {
    3.  *   this.val = x;
    4.  *   this.left = null;
    5.  *   this.right = null;
    6.  * }
    7.  */
    8. /**
    9.  * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    10.  *
    11.  *
    12.  * @param root TreeNode类
    13.  * @return bool布尔型
    14.  */
    15. function isCompleteTree(root) {
    16.     // write code here
    17.     if (root == null) return true;
    18.  
    19.     const queue = [];
    20.     queue.push(root);
    21.  
    22.     let flag = false; //是否遇到空节点
    23.     while (queue.length) {
    24.         const node = queue.shift();
    25.         if (node == null) {
    26.             //如果遇到某个节点为空，进行标记，代表到了完全二叉树的最下层
    27.             flag = true;
    28.             continue;
    29.         }
    30.  
    31.         if (flag == true) {
    32.             //若是后续还有访问，则说明提前出现了叶子节点，不符合完全二叉树的性质。
    33.             return false;
    34.         }
    35.  
    36.         queue.push(node.left);
    37.         queue.push(node.right);
    38.     }
    39.     return true;
    40. }
    41. module.exports = {
    42.     isCompleteTree: isCompleteTree,
    43. };

    判断平衡二叉树

    平衡二叉树是左子树的高度与右子树的高度差的绝对值小于等于1，同样左子树是平衡二叉树，右子树为平衡二叉树。

    递归Math.max(getMaxDepth(root.left)+1,getMaxDepth(root.right)+1)

    1. /* function TreeNode(x) {
    2.     this.val = x;
    3.     this.left = null;
    4.     this.right = null;
    5. } */
    6. function IsBalanced_Solution(pRoot)
    7. {
    8.     if(!pRoot) return true;
    9.     // write code here
    10.     return (Math.abs(getMaxDepth(pRoot.left) - getMaxDepth(pRoot.right)) <=1) && IsBalanced_Solution(pRoot.left) && IsBalanced_Solution(pRoot.right)
    11. }
    12.  
    13. function getMaxDepth(root) {
    14.     if(!root) return 0;
    15.     return Math.max(getMaxDepth(root.left)+1,getMaxDepth(root.right)+1)
    16. }
    17. module.exports = {
    18.     IsBalanced_Solution : IsBalanced_Solution
    19. };

    判断对称二叉树

    递归deep(left.left, right.right) && deep(left.right, right.left)

    1. /* function TreeNode(x) {
    2.     this.val = x;
    3.     this.left = null;
    4.     this.right = null;
    5. } */
    6. let flag = true;
    7. function deep(left, right) {
    8.     if (!left && !right) return true; //可以两个都为空
    9.     if (!right||!left|| left.val !== right.val) {//只有一个为空或者节点值不同，必定不对称
    10.         return false;
    11.     }
    12.     return deep(left.left, right.right) && deep(left.right, right.left); //每层对应的节点进入递归比较
    13. }
    14. function isSymmetrical(pRoot) {
    15.     return deep(pRoot, pRoot);
    16. }
    17. module.exports = {
    18.     isSymmetrical: isSymmetrical,
    19. };

    翻转/生成镜像二叉树

    递归交换左右

    先序遍历

    1. /*
    2.  * function TreeNode(x) {
    3.  *   this.val = x;
    4.  *   this.left = null;
    5.  *   this.right = null;
    6.  * }
    7.  */
    8. /**
    9.  * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    10.  *
    11.  * 
    12.  * @param pRoot TreeNode类 
    13.  * @return TreeNode类
    14.  */
    15. function Mirror( pRoot ) {
    16.     
    17.     function traversal(root){
    18.         if(root===null) return ;
    19.         //交换左右孩子
    20.         let temp = root.left;
    21.         root.left = root.right;
    22.         root.right = temp;
    23.  
    24.         traversal(root.left);
    25.         traversal(root.right);
    26.         return root;
    27.     }
    28.     
    29.     return traversal(pRoot);
    30.     // write code here
    31. }
    32. module.exports = {
    33.     Mirror : Mirror
    34. };

    两节点的最近公共祖先

     如果从两个节点往上找，每个节点都往上走，一直走到根节点，那么根节点到这两个节点的连线肯定有相交的地方，

    如果从上往下走，那么最后一次相交的节点就是他们的最近公共祖先节点。

    递归后序遍历

    1. /*
    2.  * function TreeNode(x) {
    3.  *   this.val = x;
    4.  *   this.left = null;
    5.  *   this.right = null;
    6.  * }
    7.  */
    8.  
    9. /**
    10.  *
    11.  * @param root TreeNode类
    12.  * @param o1 int整型
    13.  * @param o2 int整型
    14.  * @return int整型
    15.  */
    16. function dfs(root, o1, o2) {
    17.     if (root == null || root.val == o1 || root.val == o2) {
    18.         return root;
    19.     }
    20.     //递归遍历左子树
    21.     let left = dfs(root.left, o1, o2);
    22.     //递归遍历右子树
    23.     let right = dfs(root.right, o1, o2);
    24.     //如果left、right都不为空，那么代表o1、o2在root的两侧，所以root为他们的公共祖先
    25.     if (left && right) return root;
    26.     //如果left、right有一个为空，那么就返回不为空的那一个
    27.     return left != null ? left : right;
    28. }

    构造二叉树

    从中序与前/后序遍历序列构造二叉树

    1. //前
    2. var buildTree = function(preorder, inorder) {
    3.   if (!preorder.length) return null;
    4.   const rootVal = preorder.shift(); // 从前序遍历的数组中获取中间节点的值， 即数组第一个值
    5.   const index = inorder.indexOf(rootVal); // 获取中间节点在中序遍历中的下标
    6.   const root = new TreeNode(rootVal); // 创建中间节点
    7.   root.left = buildTree(preorder.slice(0, index), inorder.slice(0, index)); // 创建左节点
    8.   root.right = buildTree(preorder.slice(index), inorder.slice(index + 1)); // 创建右节点
    9.   return root;
    10. };
    11. //后
    12. var buildTree = function(inorder, postorder) {
    13.     if (!inorder.length) return null;
    14.     const rootVal = postorder.pop(); // 从后序遍历的数组中获取中间节点的值， 即数组最后一个值
    15.     let rootIndex = inorder.indexOf(rootVal); // 获取中间节点在中序遍历中的下标
    16.     const root = new TreeNode(rootVal); // 创建中间节点
    17.     root.left = buildTree(inorder.slice(0, rootIndex), postorder.slice(0, rootIndex)); // 创建左节点
    18.     root.right = buildTree(inorder.slice(rootIndex + 1), postorder.slice(rootIndex)); // 创建右节点
    19.     return root;
    20. };

    最大二叉树：二叉树的根是数组中的最大元素（递归定义）

    1. var constructMaximumBinaryTree = function (nums) {
    2.     const BuildTree = (arr, left, right) => {
    3.         if (left > right)
    4.             return null;
    5.         let maxValue = -1;
    6.         let maxIndex = -1;
    7.         for (let i = left; i <= right; ++i) {
    8.             if (arr[i] > maxValue) {
    9.                 maxValue = arr[i];
    10.                 maxIndex = i;
    11.             }
    12.         }
    13.         let root = new TreeNode(maxValue);
    14.         root.left = BuildTree(arr, left, maxIndex - 1);
    15.         root.right = BuildTree(arr, maxIndex + 1, right);
    16.         return root;
    17.     }
    18.     let root = BuildTree(nums, 0, nums.length - 1);
    19.     return root;
    20. };

    二叉搜索树：左<根<右（按中序遍历有序的树）

    删除二叉搜索树中的节点

    1. /**
    2.  * Definition for a binary tree node.
    3.  * function TreeNode(val, left, right) {
    4.  *     this.val = (val===undefined ? 0 : val)
    5.  *     this.left = (left===undefined ? null : left)
    6.  *     this.right = (right===undefined ? null : right)
    7.  * }
    8.  */
    9. /**
    10.  * @param {TreeNode} root
    11.  * @param {number} key
    12.  * @return {TreeNode}
    13.  */
    14. var deleteNode = function(root, key) {
    15.     if (!root) return null;
    16.     if (key > root.val) {
    17.         root.right = deleteNode(root.right, key);
    18.         return root;
    19.     } else if (key < root.val) {
    20.         root.left = deleteNode(root.left, key);
    21.         return root;
    22.     } else {
    23.         // 场景1: 该节点是叶节点
    24.         if (!root.left && !root.right) {
    25.             return null
    26.         }
    27.         // 场景2: 有一个孩子节点不存在
    28.         if (root.left && !root.right) {
    29.             return root.left;
    30.         } else if (root.right && !root.left) {
    31.             return root.right;
    32.         }
    33.         // 场景3: 左右节点都存在
    34.         const rightNode = root.right;
    35.         // 获取最小值节点
    36.         const minNode = getMinNode(rightNode);
    37.         // 将待删除节点的值替换为最小值节点值
    38.         root.val = minNode.val;
    39.         // 删除最小值节点
    40.         root.right = deleteNode(root.right, minNode.val);
    41.         return root;
    42.     }
    43. };
    44. function getMinNode(root) {
    45.     while (root.left) {
    46.         root = root.left;
    47.     }
    48.     return root;
    49. }

    修剪二叉搜索树

    修剪二叉搜索树，使得所有节点的值在[L, R]中 (R>=L) 

    1. var trimBST = function (root,low,high) {
    2.     if(root === null) {
    3.         return null;
    4.     }
    5.     if(root.val < low) {
    6.         let right = trimBST(root.right, low, high);
    7.         return right;
    8.     }
    9.     if(root.val > high) {
    10.         let left = trimBST(root.left, low, high);
    11.         return left;
    12.     }
    13.     root.left = trimBST(root.left, low, high);
    14.     root.right = trimBST(root.right, low, high);
    15.     return root;
    16.  }

    有序数组转换为平衡二叉搜索树

    left, right比arr.slice高效

    Math.floor(left + (right - left) / 2)

    1. var sortedArrayToBST = function (nums) {
    2.     const buildTree = (Arr, left, right) => {
    3.         if (left > right)
    4.             return null;
    5.  
    6.         let mid = Math.floor(left + (right - left) / 2);
    7.  
    8.         let root = new TreeNode(Arr[mid]);
    9.         root.left = buildTree(Arr, left, mid - 1);
    10.         root.right = buildTree(Arr, mid + 1, right);
    11.         return root;
    12.     }
    13.     return buildTree(nums, 0, nums.length - 1);
    14. };

    最值、差值->有序数组的差值、最值

    二叉搜索树的最小绝对差

    二叉搜索树转换为累加树

    一个有序数组[2, 5, 13]，求从后到前的累加数组，也就是[20, 18, 13]

    累加的顺序是右中左，所以我们需要反中序遍历这个二叉树，然后顺序累加

    ’东哥带你刷二叉树（思路篇） | labuladong 的算法笔记

  • 相关阅读:
    22年PMP考试内容大改，敏捷项目管理全套资料，不看过不了！
    PDF合并工具
    java测试private
    ChatGPT、GPT-4 Turbo接口调用(stream模式）
    OpenGL：开放图形库
    KDE相关记录
    虚拟机安装Docker装载Mysql
    SQL Server数据库创建远程服务器备份计划（小白详细图文教程）
    Shell脚本编程实践——第3关：使用Shell脚本创建文件目录
    Ubuntu 16.4虚拟机 配置Hadoop集群
  • 原文地址：https://blog.csdn.net/qq_28838891/article/details/133657152