1. 上下翻转二叉树

    给你一个二叉树的根节点 root ，请你将此二叉树上下翻转，并返回新的根节点。

    你可以按下面的步骤翻转一棵二叉树：

    1. 原来的左子节点变成新的根节点

    2. 原来的根节点变成新的右子节点

    3. 原来的右子节点变成新的左子节点

      image-20230131181539687

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
var upsideDownBinaryTree = function(root) {
    if (root && root.left === null) return root;
    return fn(root, null);
};

function fn(node, pre) {
    if (node === null) return pre;
    if (node.left === null) return pre;
    const currNode = {
        val: node.left.val,
        left: node.right ? generateTree(node.right.val) : null,
        right: pre ? pre : generateTree(node.val)
    }
    return fn(node.left, currNode);
}

function generateTree(val) {
    return {
        val: val,
        left: null,
        right: null
    }
}

链表

链表相加

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

  function reverse(head){
    if(head===null) return head;
        let pre=null;
        let cur=head;
        let next=null
        while(cur){
            next=cur.next;
            cur.next=pre;
            pre=cur;
            cur=next;
        }
            head=pre;
            return head;       
    }


function addInList(head1,head2){
    if(head1===null) return head2;
    if(head2===null) return head1;

    let l1=reverse(head1);
    let l2=reverse(head2);

    let dum=new ListNode(-1);
    let p=dum;

    let ca=0;

    while(l1||l2){
        let sum=ca;
        if(l1){
            sum+=l1.val;
            l1=l1.next;
        }
          if(l2){
            sum+=l2.val;
            l2=l2.next;
        }
        ca=Math.floor(sum/10);
        let val=sum%10;
        p.next=new ListNode(val);
        p=p.next;

    }
    if(ca>0) p.next=new ListNode(ca);
    return reverse(dum.next); 
}



module.exports = {
    addInList : addInList
};

链表排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
function sortInList(head) {
  if(head==null || head.next==null)  return head;  //0个元素或者1个元素
  
  let slow = head,
      fast = head.next;
  
  //快慢指针寻找链表中点->slow
  while(fast!=null && fast.next!=null){
    fast = fast.next.next;
    slow = slow.next;
  }
  let temp = slow.next;//中间右边的节点
  slow.next = null;
  
  //递归左右两边进行排序
  let left  = sortInList(head);
  let right = sortInList(temp);
  
  let empty = {};
  let pre = empty;
  
  //合并left和right两个链表
  while(left!=null && right!=null){
    if(left.val < right.val){
      pre.next = left;
      left = left.next;
    }else{
      pre.next = right;
      right = right.next;
    }
    pre = pre.next;
  }
  
  pre.next = left!=null ? left : right;//添加两块剩余的
  return empty.next;
}
module.exports = {
  sortInList: sortInList,
};