Java class TreeNode is defined as below:

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

Suppose you only have the reference of the root, please write a method that returns a deep copy of the binary tree. Your method returns the root of the deep copy. Your algorithm should have time complexity of O( n ).

The code should be in java.