【JavaScript】LeetCode：46-50

46 翻转二叉树

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

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 {TreeNode}
12. */
13. var invertTree = function(root) {
14.     if(root == null){
15.         return root;
16.     }
17.     let tmp = new TreeNode();
18.     tmp = root.left;
19.     root.left = root.right;
20.     root.right = tmp;
21.     invertTree(root.left);
22.     invertTree(root.right);
23.     return root;
24. };

复制代码

47 对称二叉树

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

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 {boolean}
12. */
13. var isSymmetric = function(root) {
14.     var compare = function(left, right){
15.         if(left == null && right != null){
16.             return false;
17.         }else if(left != null && right == null){
18.             return false;
19.         }else if(left == null && right == null){
20.             return true;
21.         }else if(left.val != right.val){
22.             return false;
23.         }
24.         let leftnode = compare(left.left, right.right);
25.         let rightnode = compare(left.right, right.left);
26.         return leftnode && rightnode;
27.     }
28.     if(root == null){
29.         return true;
30.     }
31.     return compare(root.left, root.right);
32. };

复制代码

48 二叉树的直径

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

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 diameterOfBinaryTree = function(root) {
14.     var deep = function(root){
15.         if(root == null){
16.             return 0;
17.         }
18.         let left = deep(root.left);
19.         let right = deep(root.right);
20.         res = Math.max(res, left + right + 1);
21.         return Math.max(left, right) + 1;
22.     };
23.     let res = 1;
24.     deep(root);
25.     return res - 1;
26. };

复制代码

49 二叉树的层序遍历

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

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 levelOrder = function(root) {
14.     if(root == null){
15.         return [];
16.     }
17.     let queue = [];  
18.     let res = [];
19.     queue.push(root);
20.     while(queue.length != 0){
21.         let layer = [];
22.         let size = queue.length;
23.         while(size--){
24.             let node = queue.shift();
25.             if(node.left){
26.                 queue.push(node.left);
27.             }
28.             if(node.right){
29.                 queue.push(node.right);
30.             }
31.             layer.push(node.val);
32.         }
33.         res.push(layer);
34.     }
35.     return res;
36. };

复制代码

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

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

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 {number[]} nums
11. * @return {TreeNode}
12. */
13. var sortedArrayToBST = function(nums) {
14.     var traversal = function(nums, left, right){
15.         if(left > right){
16.             return null;
17.         }
18.         let mid = Math.floor((left + right) / 2);
19.         let node = new TreeNode(nums[mid]);
20.         node.left = traversal(nums, left, mid - 1);
21.         node.right = traversal(nums, mid + 1, right);
22.         return node;
23.     }
24.     return traversal(nums, 0, nums.length - 1);
25. };

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。