前端Jeek

树训练

算法

🌙 树 (opens new window)

🌙 1.二叉树的前序遍历 (opens new window)

  • 迭代法
/**
 * 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 preorderTraversal = function(root) {
    let res = []

    if(!root) return res

    let stack = []
    let p = root
    stack.push(root)

    while(stack.length > 0) {
        p = stack.pop()

        res.push(p.val) // 根

        if(p.right) {
            stack.push(p.right) // 右先入栈
        }
        
        if(p.left) {
            stack.push(p.left) // 左后入栈
        }
    }

    return res
};
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
  • 递归法
/**
 * 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 preorderTraversal = function(root) {
    var res = [];
    preOrder(root, res);

    return res;
};

var preOrder = function(root, res) {
    if(!root) return;
    // 根 - 左 - 右
    res.push(root.val);
    preOrder(root.left, res);
    preOrder(root.right, res);
}
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

🌙 2.二叉树的中序遍历 (opens new window)

  • 迭代法
/**
 * 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 inorderTraversal = function(root) {
    let res = []
    if(!root) return res

    let stack = []
    let cur = root
    while(cur || stack.length > 0) {
        if(cur) {  // 指针来访问节点，访问到最底层
            stack.push(cur) // 根先入栈
            cur = cur.left  // 左接着入栈
        } else {
            cur = stack.pop() // 出栈：左后进先出， 根接着出栈
            res.push(cur.val) // 记录
            cur = cur.right // 右
        }
    }

    return res
};
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
  • 递归法
/**
 * 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 inorderTraversal = function(root) {
    var res = [];
    inOrder(root, res);

    return res;
};

var inOrder = function(root, res) {
    if(!root) return;
    // 左 - 根 - 右
    inOrder(root.left, res);
    res.push(root.val);
    inOrder(root.right, res);
}
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

🌙 3.二叉树的后序遍历 (opens new window)

  • 迭代法
/**
 * 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 postorderTraversal = function(root) {
    let res = []

    if(!root) return res
    let stack = []
    stack.push(root)

    while(stack.length > 0) {
        let p = stack.pop()
        res.push(p.val) // 根

        // 相对于前序遍历，这更改一下入栈顺序
        if(p.left) {
            stack.push(p.left) // 左
        }
        if(p.right) {
            stack.push(p.right) // 右
        }
    }
    
    // 根 - 右 - 左 --》 左 - 右 - 根
    res.reverse()

    return res
};
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
  • 递归法
/**
 * 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 postorderTraversal = function(root) {
    var res = [];
    postOrder(root, res);

    return res;
};

var postOrder = function(root, res) {
    if(!root) return;
    // 左 - 右 - 根
    postOrder(root.left, res);
    postOrder(root.right, res);
    res.push(root.val)
}
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

🌙 4.二叉树的层序遍历 (opens new window)

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function(root) {
    var res = [];
    // 广度优先遍历
    bfs(root, res);

    return res;
};

var bfs = function(root, res) {
    if(!root) return;
    // 根入队列
    var queue = [root];

    while(queue.length > 0) {
        // 记录size
        var size = queue.length;
        // 保存当前层数据
        var data = [];
        // 此处使用size，不要使用queue.length,因为他是一直变化的
        for(var i=0; i < size; i++) {
            // 出队列
            var cur = queue.shift();
            // 保存数据
            data.push(cur.val);
            // 左子树入队列
            if(cur.left) queue.push(cur.left);
            // 右子树入队列
            if(cur.right) queue.push(cur.right);
        }

        res.push(data);
    }
}
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

🌙 5.二叉树的最大深度 (opens new window)

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function(root) {
    if(!root) return 0;

    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right))
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

二叉树的最小深度 (opens new window)

/**
 * 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 minDepth = function(root) {
    if(!root) return 0

    let l = minDepth(root.left)
    let r = minDepth(root.right)
    if(!root.left) return r + 1
    if(!root.right) return l + 1
    return Math.min(l, r) + 1
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

🌙 6.对称二叉树 (opens new window)

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function(root) {
    if(!root) return true;

    return helper(root.left, root.right);
};

// 判断左右节点是否对称
var helper = function(root1, root2) {
    // 都不存在
    if(!root1 && !root2) return true;
    // 有一个不存在
    if(!root1 || !root2) return false;
    // 都存在，值不同
    if(root1.val !== root2.val) return false;
    // 都存在，值相同,继续比较子节点
    return helper(root1.left, root2.right) && helper(root1.right, root2.left);
}
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

🌙 7.验证二叉搜索树 (opens new window)

  • 递归：

    /**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isValidBST = function(root) {
    return helper(root, -Infinity, Infinity);
};

var helper = function(root, lower, higher) {
    if(!root) return true;
    if(root.val <= lower || root.val >= higher) return false;
    // 维护这个最值，左节点的最大值为root.val；右节点的最小值为root.val
    return helper(root.left, lower, root.val) && helper(root.right, root.val, higher);
}
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21

  • 迭代：中序遍历二叉搜索树的结果序列是一个升序序列

    /**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isValidBST = function(root) {
   // 中序遍历
   let inorder = -Infinity;
   let stack = [];

   while(root !== null || stack.length) {
       // 先遍历左子树
       while(root !== null) {
           stack.push(root);
           root = root.left;
       }
       // 左子树出栈
       root = stack.pop();
        // 如果中序遍历得到的节点的值小于等于前一个 inorder，说明不是二叉搜索树
       if(root.val <= inorder) return false;
       inorder = root.val;
       root = root.right;
   }
   return true;
};
    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

🌙 8.二叉搜索树的最近公共祖先 (opens new window)

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function(root, p, q) {
        //如果根节点和p,q的差相乘是正数，说明这两个差值要么都是正数要么都是负数，也就是说
        //他们肯定都位于根节点的同一侧，就继续往下找
        while ((root.val - p.val) * (root.val - q.val) > 0) {
            root = p.val < root.val ? root.left : root.right;
        }
        //如果相乘的结果是负数，说明p和q位于根节点的两侧，如果等于0，说明至少有一个就是根节点
        return root;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

🌙 9.二叉树的最近公共祖先 (opens new window)

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function(root, p, q) {
    if(root === null || root === p || root === q) return root;
    
    // 分别在left和right中找p和q的公共祖先
    var left = lowestCommonAncestor(root.left, p, q);
    var right = lowestCommonAncestor(root.right, p, q);
    
    //如果left为空，说明这两个节点在cur结点的右子树上，我们只需要返回右子树查找的结果即可
    if(left === null) return right;
    //同理
    if(right === null) return left;
    
	//如果left和right都不为空，说明这两个节点一个在root的左子树上一个在root的右子树上，
    //我们只需要返回root结点即可。	
    return root;

};
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

🌙 10.平衡二叉树 (opens new window)

/**
 * 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 isBalanced = function(root) {
    if(!root) return true

    let leftDepth = getDepth(root.left)
    let rightDepth = getDepth(root.right)

    return Math.abs(leftDepth - rightDepth) <= 1 && isBalanced(root.left) && isBalanced(root.right)
};

function getDepth(root) {
    if(!root) return 0

    return Math.max(getDepth(root.left), getDepth(root.right)) + 1
}
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

🌙 11.路径总和 (opens new window)

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} sum
 * @return {boolean}
 */
var hasPathSum = function(root, sum) {
    if(!root) return false;

    if(!root.left && !root.right && root.val === sum) return true;

    return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

🌙 12.从中序与后序遍历序列构造二叉树 (opens new window)

/**
 * 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[]} inorder
 * @param {number[]} postorder
 * @return {TreeNode}
 */
var buildTree = function (inorder, postorder) {
  return build(inorder, postorder, 0, inorder.length - 1, 0, postorder.length - 1)
};

function build(inorder, postorder, is, ie, ps, pe) {
  // 递归边界
  if (is > ie || ps > pe) return null

  // 在后序遍历中找到root节点
  let rootVal = postorder[pe]
  let root = new TreeNode(rootVal)
  // 如果就一个节点
  if (ps === pe) return root

  // 在inorder中根据rootVal找到root对应的索引，将tree一分为二
  let rootIndex = inorder.indexOf(rootVal)

  // 分别构建左右子树
  root.left = build(inorder, postorder, is, rootIndex - 1, ps, ps + (rootIndex - 1) - is)
  root.right = build(inorder, postorder, rootIndex + 1, ie, pe - 1 - (ie - rootIndex - 1), pe - 1)

  return root
}
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

🌙 13.从前序与中序遍历序列构造二叉树 (opens new window)

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
var buildTree = function(preorder, inorder) {
    return helper(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1);
};

var helper = function(preorder, inorder, preorderStart, preorderEnd, inorderStart, inorderEnd) {
    // 判断越界
    if(preorderStart > preorderEnd || inorderStart > inorderEnd) return null;
    
    // 根节点
    const rootVal = preorder[preorderStart];
    const root = new TreeNode(rootVal);

    // 判断preorder是不是只有一个节点
    if(preorderStart === preorderEnd) return root;
    // **在中序遍历中找到rootIndex,将inorder分为左右两个子节点**
    const rootIndex = inorder.indexOf(rootVal);

    root.left = helper(preorder, inorder, preorderStart + 1, preorderStart + 1 + ((rootIndex - 1) - inorderStart), inorderStart, rootIndex - 1); // (rootIndex - 1) - inorderStart)即左子树长度

    root.right = helper(preorder, inorder,(preorderEnd - (inorderEnd - (rootIndex + 1))),preorderEnd, rootIndex + 1, inorderEnd); // (inorderEnd - (rootIndex + 1)) 即右子树长度

    return root;
}
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

🌙 14.从前序和后序遍序列历构造二叉树 (opens new window)

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {number[]} pre
 * @param {number[]} post
 * @return {TreeNode}
 */
var constructFromPrePost = function(pre, post) {
    return helper(pre, post, 0, pre.length - 1, 0, post.length - 1);
};

var helper = function(pre, post, preStart, preEnd, postStart, postEnd) {
    // 判断越界
    if(preStart > preEnd || postStart > postEnd) return null;

    // 根节点
    const rootVal = pre[preStart];
    const root = new TreeNode(rootVal);

    // 判断是不是只有一个节点
    if(preStart === preEnd) return root;

    // 先在preorder中找到左子树的leftRootVal
    const leftRootVal = pre[preStart + 1];
    // **然后在post中找到leftRootIndex, 然后根据这个index将post分为左右两个子节点**
    const index = post.indexOf(leftRootVal);

    root.left = helper(pre, post, preStart + 1, preStart + 1 + (index - postStart) , postStart, index); // (index - postStart) 即左子树长度
    root.right = helper(pre, post, (preEnd - (postEnd - 1 - (index + 1))), preEnd, index + 1, postEnd - 1);  // (postEnd - 1 - (index + 1))即右子树长度

    return root;
}
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

“看我就够了”三种遍历方式构造二叉树的通解 (opens new window)

🌙 15.二叉搜索树转为单链表 (opens new window)

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
// 正确解法1
var convertBiNode1 = function(root) {
    let head = new TreeNode(null);
    let pre = head;
    var inOrder = function(root) {
        if(!root) return;
        // 左 - 右 - 根
        inOrder(root.left);
        root.left = null;
        pre.right = root;
        pre = root;
        inOrder(root.right);
    }
    inOrder(root);
    return head.right;
};

// 将inOrder提取出来：
// 错误解法
var convertBiNode = function(root) {
    let head = new TreeNode(null);
    let pre = head;
    inOrder(root, pre);
    return head.right;
};

var inOrder = function(root, pre) {
        if(!root) return;
        // 左 - 根 - 右 
        inOrder(root.left, pre);

        root.left = null;
        pre.right = root;
        pre = root;

        inOrder(root.right, pre);
    }

// 正确解法2
var convertBiNode2 = function(root) {
    let head = new TreeNode(null);
    inOrder(root, head);
    return head.right;
};

var pre;
var inOrder = function(root, head) {
        if(!root) return;
    
    	pre = head;
        // 左 - 根 - 右 
        inOrder(root.left, pre);

        root.left = null;
        pre.right = root;
        pre = root;

        inOrder(root.right, pre);
    }

// 正确解法3
var convertBiNode = function(root) {
    let head = new TreeNode(null);
    inOrder(root, head);
    return head.right;
};

// var pre;
var inOrder = function(root, pre) {
        if(!root) return pre;
        // 左 - 根 - 右 
        pre = inOrder(root.left, pre);

        root.left = null;
        pre.right = root;
        pre = root;

        pre = inOrder(root.right, pre);

        return pre;
    }
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92

🌙 16.二叉树转为单链表 (opens new window)

/**
 * 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 {void} Do not return anything, modify root in-place instead.
 */
var flatten = function(root) {
    let pre = new TreeNode();;

    var preOrder = function(root) {
        if(!root) return;
        let left = root.left;
        let right = root.right;

        root.left = null;
        pre.right = root;
        pre = root;

        preOrder(left);
        preOrder(right);
    }
    
    // 调用
    preOrder(root);
    
    root = pre.right;
};
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

🌙 17.二叉搜索树转为双向链表 (opens new window)

  • 思路：先中序遍历二叉树，在将结果转为循环双向链表

    /**
 * // Definition for a Node.
 * function Node(val,left,right) {
 *    this.val = val;
 *    this.left = left;
 *    this.right = right;
 * };
 */
/**
 * @param {Node} root
 * @return {Node}
 */
var treeToDoublyList = function(root) {
    if(!root) return root;
    
    let res = [];

    inOrder(root, res);

    // 方式一：
    // var head = res[0];
    // var tail = res[res.length - 1];
    // tail.right = head;
    // head.left = tail;
    // for(var i=1; i < res.length; i++) {
    //     // 更改left和right指向
    //     head.right = res[i];
    //     res[i].left = head;
    //     head = res[i];
    // }
    
    // 方式二：
    // var pre = null;
    // var head = null;

    // for(var i=0; i < res.length; i++) {
    //    if(pre) {
    //       // 更改left和right指向
    //        pre.right = res[i];
    //        res[i].left = pre;
    //    } else {
    //        head = res[i]
    //    }
    //    pre = res[i];
    //}
    
    // 方式三：
    var pre = res[0];
    var head = res[0];
    
    for(var i=1; i < res.length; i++) {
        // 更改left和right指向
        pre.right = res[i];
        res[i].left = pre;
        
        pre = res[i];
    }
    
    // 循环完毕，pre指向了最后一个节点
    // 处理首尾节点
    pre.right = head;
    head.left = pre;

    return res[0];
};

var inOrder = function(root, res) {
    if(!root) return;
    var left = root.left;
    var right = root.right;
    // 左 - 根 - 右
    inOrder(left, res);
    res.push(root);
    inOrder(right, res);
}
    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
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75

  • 改进：在中序遍历的过程中把二叉树转为双向链表，然后再处理首尾链表，转为循环双向链表

    /**
 * // Definition for a Node.
 * function Node(val,left,right) {
 *    this.val = val;
 *    this.left = left;
 *    this.right = right;
 * };
 */
/**
 * @param {Node} root
 * @return {Node}
 */
var treeToDoublyList = function(root) {
    if(!root) return root;
    
    let head = null;
    let tail = null;

    var inOrder = function(cur) {
        if(!cur) return;
        
        // 左 - 根 - 右
        inOrder(cur.left);
        
        // 修改为链表
        if(!head) {
            // 记录第一个节点
            head = cur;
        } else {
            tail.right = cur;
            cur.left = tail;
        }
        // 保存当前节点
        tail = cur;

        inOrder(cur.right);
	}
    
    inOrder(root);
    head.left = tail;
    // 此时pre指向了最后一个节点
    tail.right = head;

    return head;
};
    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

🌙 18.有序链表转换二叉搜索树 (opens new window)

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * 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 {ListNode} head
 * @return {TreeNode}
 */
var sortedListToBST = function(head) {
    // 链表为空
    if(!head) return null;

    // 链表只有一个节点
    if(!head.next) return new TreeNode(head.val);

    // 找到中继节点
    var pre = head; // pre慢slow一步
    // slow每次走一步 fast每次走两步，当fast走到终点时，slow刚好在中途
    var slow = head.next;
    var fast = head.next.next;

    while(fast && fast.next) {
        pre = pre.next;
        slow = slow.next;
        fast = fast.next.next;
    }

    // 此时pre的下一个节点就是中继节点slow，将其打断把链表一分为二
    pre.next = null;

    // 将中继节点作为树根节点
    var root = new TreeNode(slow.val);
    // 左子树开始节点
    var left = head;
    // 右子树开始节点
    var right = slow.next;

    root.left = sortedListToBST(left);
    root.right = sortedListToBST(right);

    return root;
};
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

🌙 19.搜索树中的 二分查找 (opens new window)


/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} val
 * @return {TreeNode}
 */
var searchBST = function(root, val) {
    if (root == null) return null;
    if (root.val === val) return root;
    if (root.val > val) {
        return searchBST(root.left, val);
    } else if (root.val < val) {
        return searchBST(root.right, val);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

🌙 20.N 叉树的后前序遍历 (opens new window)

给定一个 n 叉树的根节点 root ，返回 其节点值的 后序遍历（前序遍历） 。

n 叉树 在输入中按层序遍历进行序列化表示，每组子节点由空值 null 分隔（请参见示例）。
1
2
3
  • 递归
/**
 * // Definition for a Node.
 * function Node(val,children) {
 *    this.val = val;
 *    this.children = children;
 * };
 */

/**
 * @param {Node|null} root
 * @return {number[]}
 */

// 后序遍历
var postorder = function (root) {
  let res = []
  if (!root) return res
  help(root, res)

  return res
};

function help(root, res) {
  if (!root) return

  if (!root.children) {
    res.push(root.val)
    return
  }

  for (let ch of root.children) {
    help(ch, res)
  }
  res.push(root.val)
}

/**
 * // Definition for a Node.
 * function Node(val, children) {
 *    this.val = val;
 *    this.children = children;
 * };
 */

/**
 * @param {Node|null} root
 * @return {number[]}
 */
// 前序遍历
var preorder = function(root) {
  let res = []
  if(!root) return res
  help(root, res)

  return res
};

function help(root, res) {
  if(!root) return

  res.push(root.val)

  for(let ch of root.children) {
    help(ch, res)
  }
}
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
55
56
57
58
59
60
61
62
63
64
65
66
  • 迭代
/**
 * // Definition for a Node.
 * function Node(val,children) {
 *    this.val = val;
 *    this.children = children;
 * };
 */

/**
 * @param {Node|null} root
 * @return {number[]}
 */
// 后序遍历
var postorder = function (root) {
  let res = []
  if (!root) return res

  let stack = []
  stack.push(root)

  while (stack.length > 0) {
    let cur = stack.pop()
    // 后序遍历
    res.unshift(cur.val)

    if (cur.children) {
      for (let ch of cur.children) {
        stack.push(ch)
      }
    }
  }

  return res
};


/**
 * // Definition for a Node.
 * function Node(val, children) {
 *    this.val = val;
 *    this.children = children;
 * };
 */

/**
 * @param {Node|null} root
 * @return {number[]}
 */
// 先序遍历
var preorder = function(root) {
  let res = []
  if(!root) return res

  let stack = []
  stack.push(root)

  while(stack.length > 0) {
    let cur = stack.pop()
    res.push(cur.val)

    if(cur.children) {
      for(let i=cur.children.length - 1; i>=0 ;i--) {
        stack.push(cur.children[i])
      }
    }
  }

  return res
};
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

🌙 21.N 叉树的层序遍历(https://leetcode.cn/problems/n-ary-tree-level-order-traversal/description/)

给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。

树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。

示例 1：
输入：root = [1,null,3,2,4,null,5,6]
输出：[[1],[3,2,4],[5,6]]

示例 2：
输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出：[[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]
 
提示：
树的高度不会超过 1000
树的节点总数在 [0, 10^4] 之间
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * // Definition for a Node.
 * function Node(val,children) {
 *    this.val = val;
 *    this.children = children;
 * };
 */

/**
 * @param {Node|null} root
 * @return {number[][]}
 */
var levelOrder = function (root) {
  let res = []
  if (!root) return res

  let queue = []
  queue.push(root)

  while (queue.length > 0) {
    let size = queue.length
    let data = []

    for (let i = 0; i < size; i++) {
      let cur = queue.shift()
      data.push(cur.val)
      if (cur.children) {
        for (let ch of cur.children) {
          queue.push(ch)
        }
      }
    }

    res.push(data)
  }

  return res
};
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

动态规划训练