The preorder traversal of leetcode 144 binary tree and the expansion of leetcode 114 binary tree into a linked list

LeetCode 144 Preorder traversal of two tree

Title Description ：
Give you the root node of the binary tree root , Of its node value Before the order Traverse .
Example 1：
Input ：root = [1,null,2,3]
Output ：[1,2,3]

Example 2：
Input ：root = []
Output ：[]

One 、 Access the root node according to —— The left subtree —— The right subtree traverses the tree , And when you visit the left or right subtree , We traverse in the same way , Until you walk through the whole tree .

You can use the complete code ：

public List<Integer> preorderTraversal(TreeNode root) {
    
    List<Integer> ans = new ArrayList<>();
    preorder(root, ans);
    return ans;
}

private void preorder(TreeNode root, List<Integer> ans) {
    
    if (root == null) {
    
        return;
    }
    ans.add(root.val);
    preorder(root.left, ans);
    preorder(root.right, ans);
}

LeetCode 114 The binary tree is expanded into a list

Title Description ：
Give you the root node of the binary tree root , Please expand it into a single linked list ：
The expanded single linked list should also be used TreeNode , among right The child pointer points to the next node in the list , The left sub pointer is always null .
The expanded single linked list should be the same as the binary tree The first sequence traversal Same order .

Example 1：

Input ：root = [1,2,5,3,4,null,6]
Output ：[1,null,2,null,3,null,4,null,5,null,6]

Example 2：
Input ：root = []
Output ：[]

One 、 First, find... Through the current root node cur The last right node of the pre order of the left subtree predecessor, Connect this node to the right subtree ; stretch 【 take curr.left=null;curr.right=next】next Namely cur.left; Then continue to loop to the left , Connect , Traversing to the end will always stretch

• Time complexity ：O(n). among n It's the number of nodes in a binary tree . In the process of expanding to a single linked list , Each node needs to be accessed once , In the process of finding the precursor node , Each node can be accessed once more at most .
• Spatial complexity ：O(1)

You can use the complete code ：

public void flatten(TreeNode root) {
    
    TreeNode curr = root;
    while (curr != null) {
    
        if (curr.left != null) {
    
            TreeNode next = curr.left;
            TreeNode predecessor = next;
            while (predecessor.right != null) {
       //  find cur The last node before the left subtree 
                predecessor = predecessor.right;
            }
            predecessor.right = curr.right;   //  Connect cur The last node of the pre order of the subtree and the right subtree 
            curr.left = null;   //  Partial extension 
            curr.right = next;
        }
        curr = curr.right;   // cur.right Even if it is the original cur The left node , Then continue to traverse to the left , Connect the rightmost node of the left subtree with other parts 【 Traversing to the end will always stretch 】
    }
}