首页 > itarticle > [leetcode] problem 114 – flatten binary tree to linked list

[leetcode] problem 114 – flatten binary tree to linked list

admin 11月 13, 2020 0

Given a binary tree, flatten it to a linked list in-place.

For example, given the following tree:

The flattened tree should look like:

Code

public class  {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public void flatten(TreeNode root) {
    helper(root);
}

private TreeNode helper(TreeNode root) {
    if (root == null)
        return null;

    TreeNode leftTail = helper(root.left);
    TreeNode rightTail = helper(root.right);

    if (root.left != null) {
        TreeNode temp = root.right;
        root.right = root.left;
        root.left = null;
        leftTail.right = temp;
    }

    if (rightTail != null)
        return rightTail;
    else if (leftTail != null)
        return leftTail;
    else
        return root;
}