Given the root of a binary tree, flatten the tree into a "linked list":
The "linked list" should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null.
The "linked list" should be in the same order as a pre-order traversal of the binary tree.
The number of nodes in the tree is in the range [0, 2000].
-100 <= Node.val <= 100
Follow up: Can you flatten the tree in-place (with O(1) extra space)?
Solutions
Solution 1: Find Predecessor Node
The visit order of preorder traversal is "root, left subtree, right subtree". After the last node of the left subtree is visited, the right subtree node of the root node will be visited next.
Therefore, for the current node, if its left child node is not null, we find the rightmost node of the left subtree as the predecessor node, and then assign the right child node of the current node to the right child node of the predecessor node. Then assign the left child node of the current node to the right child node of the current node, and set the left child node of the current node to null. Then take the right child node of the current node as the next node and continue processing until all nodes are processed.
The time complexity is $O(n)$, where $n$ is the number of nodes in the tree. The space complexity is $O(1)$.
1 2 3 4 5 6 7 8 91011121314151617181920
# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclassSolution:defflatten(self,root:Optional[TreeNode])->None:""" Do not return anything, modify root in-place instead. """whileroot:ifroot.left:pre=root.leftwhilepre.right:pre=pre.rightpre.right=root.rightroot.right=root.leftroot.left=Noneroot=root.right
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */funcflatten(root*TreeNode){forroot!=nil{ifroot.Left!=nil{pre:=root.Leftforpre.Right!=nil{pre=pre.Right}pre.Right=root.Rightroot.Right=root.Leftroot.Left=nil}root=root.Right}}
/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } *//** * @param {TreeNode} root * @return {void} Do not return anything, modify root in-place instead. */varflatten=function(root){while(root){if(root.left){letpre=root.left;while(pre.right){pre=pre.right;}pre.right=root.right;root.right=root.left;root.left=null;}root=root.right;}};
Solution 2
1 2 3 4 5 6 7 8 910111213141516171819202122
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */funcflatten(root*TreeNode){forroot!=nil{left,right:=root.Left,root.Rightroot.Left=nilifleft!=nil{root.Right=leftforleft.Right!=nil{left=left.Right}left.Right=right}root=root.Right}}