链表 END 21.11.17

• 面试题17.12.BiNode
• • 效率太低！需要改进（待补充）
• 5927.反转偶数长度组的节点

性质 二叉搜索树的中序遍历是有序的。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def convertBiNode(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        
        #当头结点为空时返回
        if root == None:
            return root
        
        lis = []
        
        #中序遍历
        def dfs(root):
            if not root:
                return
            dfs(root.left) 
            lis.append(root.val)
            dfs(root.right)
            
        dfs(root)
        
        #构造根节点
        newRoot = TreeNode(lis[0])
        copyRoot = newRoot
        
        for i in range(1, len(lis)):
            newRoot.right = TreeNode(lis[i]) //注意写法
            newRoot = newRoot.right
            
        return copyRoot

执行用时：108 ms, 在所有 Python 提交中击败了9.62%的用户
内存消耗：36.2 MB, 在所有 Python 提交中击败了7.69%的用户

class Solution {
    public TreeNode convertBiNode(TreeNode root) {
        if (root == null){
            return root;
        }
        List list = new ArrayList();
        dfs(root, list);
        TreeNode newRoot = new TreeNode(list.get(0));
        TreeNode copyRoot = newRoot;
        for (int i = 1; i < list.size(); i++){
            newRoot.left = null;
            newRoot.right = new TreeNode(list.get(i)); //注意写法
            newRoot = newRoot.right;
        }
        return copyRoot;
    }
    public void dfs(TreeNode root, List list) {
        if (root == null){
            return;
        }
        dfs(root.left, list); 
        list.add(root.val);
        dfs(root.right, list);
    }
}

执行用时：5 ms, 在所有 Java 提交中击败了8.26%的用户
内存消耗：44.1 MB, 在所有 Java 提交中击败了28.05%的用户

逆中序遍历

一边递归一边形成链表

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def reverseEvenLengthGroups(self, head):
        """
        :type head: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        n = 0
        pre = None
        cur = head

        while cur:

            n = n + 1
            i = 0
            temp = cur 

            while i < n and temp :
                i = i + 1
                temp = temp.next
            
            if i % 2:
                for k in range(i):
                    pre = cur
                    cur = cur.next
            else:
                for j in range(i - 1):
                    pre.next, cur.next.next, cur.next = cur.next, pre.next, cur.next.next
            	pre = cur 
            	cur = cur.next
                
        return head