反转二叉树

LetCode 226

从三个结点分析.png

public class TreeNode {
    int val;
// 这里仅仅表示引用，会发生变化
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

public class T1 {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }

        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);
        root.left = right;
        root.right = left;
        return root;
    }
}

执行过程.png

从图中可以看出，只有根节点的树，翻转后不会变化。返回的是子树根节点的地址，当子树递归完之后，双亲结点的地址引用将会发生交换，也就是翻转。