I was trying to find a solution for inverting a binary tree using iteration, but it seems that this solution doesn't work. Can anyone tell me why this wouldn't work? I know there are different solutions, but this was my first one and I feel like it should work. My initial idea is that I want to pop two child nodes every iteration and swap those because they are two sibling nodes until I have swapped every node in the tree. I feel like it has something to do with references because the output is just the original tree. My guess is that the stack is just storing copies of the nodes so it's doing the swapping, but it's not actually swapping anything in the original tree. If that's the case, how would I fix that? I know that maybe in c we could use reference types or something like that, but how does can I do that in java?

Thank you!

    public TreeNode invertTree(TreeNode root) {
        if (root == null) return root;
        Stack<TreeNode> s = new Stack<>();
        s.push(root.left);
        s.push(root.right);
        
        while (!s.empty()) {
             TreeNode nd1 = s.pop();
             TreeNode nd2 = s.pop();
             TreeNode temp = nd1;
             nd1 = nd2;
             nd2 = temp;
             if (nd1 != null && nd2 != null) {
                 s.push(nd1.left);
                 s.push(nd1.right);
                 s.push(nd2.left);
                 s.push(nd2.right);
             } else if (nd1 == null && nd2 != null) {
                 s.push(nd2.left);
                 s.push(nd2.right);
             } else if (nd2 == null && nd1 != null) {
                 s.push(nd1.left);
                 s.push(nd1.right);
             }
        }
        return root;
    }

}

CodePudding user response：

We can invert tree level by level.

public TreeNode invertTree(TreeNode root) {
    if (root == null) {
        return null;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        TreeNode temp = node.left;
        node.left = node.right;
        node.right = temp;
        if (node.left != null) {
            queue.offer(node.left);
        }
        if (node.right != null) {
            queue.offer(node.right);
        }
    }
    return root;
}

CodePudding user response：

The intuitive recursive solution is:

    public TreeNode invertTree(TreeNode root) {
        if (root != null) {
            TreeNode r = root.right;
            root.right = root.left;
            root.left = r;
            invertTree(root.left);
            invertTree(root.right);
        }
        return root;
    }

Now we would like to avoid recursion, and at first glance we need to do exactly the same - swap left and right and put them into a stack, below is top-down solution:

    public TreeNode invertTree(TreeNode root) {
        Deque<TreeNode> stack = new LinkedList<>();
        stack.add(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pollFirst();
            if (node != null) {
                TreeNode r = node.right;
                node.right = node.left;
                node.left = r;
                stack.addFirst(node.right);
                stack.addFirst(node.left);
            }
        }
        return root;
    }

if we would like to implement bottom-up solution it would be:

    public TreeNode invertTree(TreeNode root) {
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode current = root;
        while (!stack.isEmpty() || current != null) {
            while (current != null) {
                stack.addFirst(current);
                current = current.left;
            }
            TreeNode pop = stack.pollFirst();
            current = pop.right;
            TreeNode tmp = pop.left;
            pop.left = pop.right;
            pop.right = tmp;
        }
        return root;
    }