二叉树翻转的递归与非递归实现（Java）

二叉树的翻转，即以根所在垂直线为对称线，对称位置的两个节点进行交换。

实现这种算法，可以有两种思路，即递归和非递归（栈）。

下面给出Java代码实现。

import java.util.Stack;

/**
 * Created by Lee on 2017/11/11.
 */
//树节点
class Node {
    int value;
    Node left;
    Node right;

    Node(int value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                ", left=" + left +
                ", right=" + right +
                '}';
    }
}
public class InvertBinaryTreeDemo {

    public static void swap(Node root){
        Node temp = root.left;
        root.left = root.right;
        root.right = temp;
    }

    //递归实现
    public static Node invert(Node root){
        if (root == null){
            return null;
        }
        root.left = invert(root.left);
        root.right = invert(root.right);
        swap(root);
        return root;
    }

    //非递归，用栈实现
    public static void invertByStack(Node root){
        Stack<Node> stack = new Stack<Node>();
        stack.push(root);
        while (!stack.empty()){
            Node node = stack.pop();
            swap(node);
            if (node.left != null){
                stack.push(node.left);
            }
            if (node.right != null){
                stack.push(node.right);
            }
        }
    }

    //测试
    public static void main(String[] args) {
        Node node0 = new Node(1);
        Node node1 = new Node(2);
        Node node2 = new Node(3);
        Node node3 = new Node(4);
        Node node4 = new Node(5);
        Node node5 = new Node(6);
        Node node6 = new Node(7);
        node0.left = node1;
        node0.right = node2;
        node1.left = node3;
        node1.right = node4;
        node2.left = node5;
        node2.right = node6;
        //invertByStack(node0);
        //invert(node0);
        System.out.println(node0);
    }
}