【JavaScript】LeetCode：46-50

文章目录

46 翻转二叉树
47 对称二叉树
48 二叉树的直径
49 二叉树的层序遍历
50 将有序数组转换为二叉搜索树

46 翻转二叉树

在这里插入图片描述

递归
前序遍历 / 后序遍历，这里给出前序遍历的代码。
遍历节点，交换左右子树。

/*** Definition for a binary tree node.* function TreeNode(val, left, right) {*     this.val = (val===undefined ? 0 : val)*     this.left = (left===undefined ? null : left)*     this.right = (right===undefined ? null : right)* }*/
/*** @param {TreeNode} root* @return {TreeNode}*/
var invertTree = function(root) {if(root == null){return root;}let tmp = new TreeNode();tmp = root.left;root.left = root.right;root.right = tmp;invertTree(root.left);invertTree(root.right);return root;
};

47 对称二叉树

在这里插入图片描述

递归
后序遍历
左子节点和右子节点分为以下几种情况：
(1) 左 = null，右 != null，不对称。
(2) 左 != null，右 = null，不对称。
(3) 左 = null，右 = null，对称。
(4) 左子节点的值 != 右子节点的值，不对称。
(5) 左子节点的值 = 右子节点的值，继续递归判断。
外侧节点的值相等和内侧节点的值相等，对称。
(1) 外侧：左子节点的左子节点，右子节点的右子节点（2 => 3）。
(2) 内测：左子节点的右子节点，右子节点的左子节点（2 => 4）。

/*** Definition for a binary tree node.* function TreeNode(val, left, right) {*     this.val = (val===undefined ? 0 : val)*     this.left = (left===undefined ? null : left)*     this.right = (right===undefined ? null : right)* }*/
/*** @param {TreeNode} root* @return {boolean}*/
var isSymmetric = function(root) {var compare = function(left, right){if(left == null && right != null){return false;}else if(left != null && right == null){return false;}else if(left == null && right == null){return true;}else if(left.val != right.val){return false;}let leftnode = compare(left.left, right.right);let rightnode = compare(left.right, right.left);return leftnode && rightnode;}if(root == null){return true;}return compare(root.left, root.right);
};

48 二叉树的直径

在这里插入图片描述

递归
遍历节点，更新以该节点为根节点的最大深度：max(该节点的左子树深度，该节点的右子树深度) + 1。
以当前节点为根节点，res = 该节点左右子树最大深度的和 + 1。
树的直径 = res - 1。

/*** Definition for a binary tree node.* function TreeNode(val, left, right) {*     this.val = (val===undefined ? 0 : val)*     this.left = (left===undefined ? null : left)*     this.right = (right===undefined ? null : right)* }*/
/*** @param {TreeNode} root* @return {number}*/
var diameterOfBinaryTree = function(root) {var deep = function(root){if(root == null){return 0;}let left = deep(root.left);let right = deep(root.right);res = Math.max(res, left + right + 1);return Math.max(left, right) + 1;};let res = 1;deep(root);return res - 1;
};

49 二叉树的层序遍历

在这里插入图片描述

队列
一层一层加入队列。
size：控制每层的节点，当size = 0时，该层节点全部遍历完成。

/*** Definition for a binary tree node.* function TreeNode(val, left, right) {*     this.val = (val===undefined ? 0 : val)*     this.left = (left===undefined ? null : left)*     this.right = (right===undefined ? null : right)* }*/
/*** @param {TreeNode} root* @return {number[][]}*/
var levelOrder = function(root) {if(root == null){return [];}let queue = [];  let res = [];queue.push(root);while(queue.length != 0){let layer = [];let size = queue.length;while(size--){let node = queue.shift();if(node.left){queue.push(node.left);}if(node.right){queue.push(node.right);}layer.push(node.val);}res.push(layer);}return res;
};

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

在这里插入图片描述

递归
奇数个节点时，中间位置节点作为中心节点。
偶数个节点时，选取左 / 右作为中心节点。
中心节点划分左右区域，左区域为左子树，右区域为右子树。

/*** Definition for a binary tree node.* function TreeNode(val, left, right) {*     this.val = (val===undefined ? 0 : val)*     this.left = (left===undefined ? null : left)*     this.right = (right===undefined ? null : right)* }*/
/*** @param {number[]} nums* @return {TreeNode}*/
var sortedArrayToBST = function(nums) {var traversal = function(nums, left, right){if(left > right){return null;}let mid = Math.floor((left + right) / 2);let node = new TreeNode(nums[mid]);node.left = traversal(nums, left, mid - 1);node.right = traversal(nums, mid + 1, right);return node;}return traversal(nums, 0, nums.length - 1);
};