“This is the 20th day of my participation in the November Gwen Challenge. See details of the event: The Last Gwen Challenge 2021”.

The binary tree expands to a linked list

You are given the root of a binary tree. Expand it into a single linked list:

  • The expanded list should also use TreeNode, with the right child pointing to the next node in the list and the left child always null.

  • The expanded list should be traversed in the same order as the binary tree.

Examples can be found on the LeetCode website.

Source: LeetCode link: leetcode-cn.com/problems/fl… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Solution one: recursion

Solve the problem recursively, and the recursive process is as follows:

  • If the current root node is null, this object is returned.
  • If both the left and right child nodes of the current root node are empty, no adjustment is required.
  • If the left subtree of the current root node is empty, only the right subtree of the current root node needs to be recursively processed.
  • If the right subtree of the current root node is empty, the left subtree of the current root node needs to be recursively processed, and then the left child of the current root node points to NULL, and the right child points to the left subtree after processing.
  • If neither of the left and right subtrees of the current root node is empty, the left and right subtrees of the current root node are recursively processed, then the left child of the root node points to NULL, the right child points to the processed left subtree, and the last node of the left subtree points to the processed right subtree.
import com.kaesar.leetcode.TreeNode;

public class LeetCode_114 {
    /** * recursively **@param root
     */
    public static void flatten(TreeNode root) {
        // If the current root node is null, this parameter is returned
        if (root == null) {
            return;
        }
        // If the left and right child nodes of the current root node are empty, no adjustment is required
        if (root.left == null && root.right == null) {
            return;
        }
        if (root.left == null) {
            If the left subtree of the current root node is empty, only the right subtree of the current root node needs to be recursively processed
            flatten(root.right);
            return;
        }
        if (root.right == null) {
            // When the right subtree of the current root node is empty, the left subtree of the current root node needs to be recursively processed, and then the left child of the current root node points to null, and the right child points to the processed left subtree
            TreeNode left = root.left;
            flatten(left);
            root.right = left;
            root.left = null;
            return;
        }
        // If the left and right subtrees of the current root node are not empty
        TreeNode left = root.left;
        // Recursively process the left subtree and find the last node after processing
        flatten(left);
        TreeNode leftLast = left;
        while(leftLast.right ! =null) {
            leftLast = leftLast.right;
        }
        TreeNode right = root.right;
        // Recursively process the right subtree
        flatten(right);
        // Finally, the left child of the root node points to null, the right child points to the processed left subtree, and the last node of the left subtree points to the processed right subtree
        root.right = left;
        leftLast.right = right;
        root.left = null;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(5);
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(4);
        root.right.right = new TreeNode(6);

        System.out.println("Before expanding to a linked list");
        root.print();
        System.out.println("Expanded as a linked list."); flatten(root); root.print(); }}Copy the code

Our life is like a roller coaster, full of high and low and exciting, we experience more, psychological construction to be strong, vision, mind to enlarge.