Java语言是怎么将半个二叉树的输出拼接在另一个半个二叉树上，实现完整的二叉树的输出的呢

Question

Java语言是怎么将半个二叉树的输出拼接在另一个半个二叉树上，实现完整的二叉树的输出的呢？这个没法循环又怎么实现的呢

Answer 1

你可以用迭代，先去判断左子树和右子树是否为空。如果其中一个为空，那么另一个就是完整的二叉树，直接返回即可。不为空的时候你可以将左子树的根节点作为完整二叉树的根节点，并将右子树的根节点作为左子树的右孩子。两个指针先后指向左右根节点，在写个循环不停的迭代。

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    
    TreeNode(int val) {
        this.val = val;
    }
}

public class BinaryTreeConcatenation {
    public TreeNode concatenateTrees(TreeNode leftTree, TreeNode rightTree) {
        if (leftTree == null) {
            return rightTree;
        }
        if (rightTree == null) {
            return leftTree;
        }
        
        TreeNode leftPointer = leftTree;
        TreeNode rightPointer = rightTree;
        
        while (leftPointer.left != null && rightPointer.right != null) {
            TreeNode leftTemp = leftPointer.left;
            TreeNode rightTemp = rightPointer.right;
            
            leftPointer.left = rightTemp;
            rightPointer.right = leftTemp;
            
            leftPointer = leftPointer.right;
            rightPointer = rightPointer.left;
        }
        
        leftPointer.left = rightPointer.right;
        return leftTree;
    }
    
    public static void main(String[] args) {
        TreeNode leftTree = new TreeNode(1);
        leftTree.left = new TreeNode(2);
        
        TreeNode rightTree = new TreeNode(3);
        rightTree.right = new TreeNode(4);
        BinaryTreeConcatenation solution = new BinaryTreeConcatenation();
        TreeNode result = solution.concatenateTrees(leftTree, rightTree);
        
        printBinaryTree(result);
    }
    
    private static void printBinaryTree(TreeNode root) {
        if (root == null) {
            return;
        }
        
        System.out.print(root.val + " ");
        printBinaryTree(root.left);
        printBinaryTree(root.right);
    }
}