This is the 28th day of my participation in Gwen Challenge

Binary tree expanded as linked list (114)

Topic describes

The root of the binary tree is root. 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.

Example 1:

Input: root = [6],2,5,3,4 1, null, output: [1, null, 2, null, 3, null, 4, null, 5, null, 6]Copy the code

Example 2:

Input: root = [] Output: []Copy the code

Example 3:

Input: root = [0] Output: [0]Copy the code

Tip:

  • The number of nodes in the tree is within the range [0, 2000]
  • -100 <= Node.val <= 100

Advanced: Can you expand the tree using the in place algorithm (O(1) extra space)?

Thought analysis

They require a sequential traversal, where the right child points to the next node in the list, and the left child is always null. We can use two auxiliary nodes for assistance, because the problem suggests us to use the in situ algorithm for solving, so we can directly convert on the nodes. We can keep adding nodes to the tail node as we iterate, and when we’re done, we can get the node we want.

The code shown

Solution a:

private TreeNode dummyHead = new TreeNode();
    private TreeNode tail = dummyHead;
    public void flatten(TreeNode root) {
        preorder(root);
    }

    private void preorder(TreeNode root){
        if(root == null) {return;
        }
        TreeNode left = root.left;
        TreeNode right = root.right;

        tail.right = root;
        tail = root;
        // All root.left needs to be null
        root.left = null;

        preorder(left);
        preorder(right);


    }
Copy the code

BiNode (Interview question 17.12)

Topic describes

The binary tree data structure TreeNode can be used to represent a one-way list (where left is left empty and right is the next list node). Implement a method, the binary search tree into a one-way list, the requirements are still consistent with the properties of the binary search tree, conversion operation should be the original address, that is, in the original binary search tree directly modify.

Returns the head node of the transformed one-way list.

Note: Some changes have been made to the original question

Example 1:

Input: [4,2,5,1,3, null, 6, 0] output: [0, null, 1, null, 2, null, 3, null, 4, null, 5, null, 6]Copy the code

Tip:

  • The number of nodes does not exceed 100000.

Thought analysis

It can be seen that the output is from small to large. That is to say, we can traverse the binary search tree using the middle-order traversal method. We can use the right pointer to point to the next node in the linked list, and the left child pointer is always null. We can use two auxiliary nodes for assistance, because the problem suggests us to use the in situ algorithm for solving, so we can directly convert on the nodes. We can keep adding nodes to the tail node as we iterate, and when we’re done, we can get the node we want.

The code shown

Solution a:

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

        if(root == null) {return null;
        }
        // P or Q themselves are common ancestors
        if(root == p || root == q){
            return root;
        }
        // Recursive search, first record left and right nodes
        TreeNode left = lowestCommonAncestor(root.left,p,q);
        TreeNode right = lowestCommonAncestor(root.right,p,q);

        // If left and right are found
        if(left ! =null&& right ! =null) {return root;
        } else if (null! = left){return left;
        } else if (null! = right){return right;
        }
        return null;
    }
Copy the code

conclusion

The binary tree is expanded as a linked list, which can be expanded by pre -, middle – and post-order traversal.