LeetCode-226-翻转二叉树

4 years ago

source link: https://segmentfault.com/a/1190000040640896
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

LeetCode-226-翻转二叉树

翻转二叉树

题目描述：翻转一棵二叉树。
示例说明请见LeetCode官网。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl...
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法一：递归

用递归的方法将二叉树翻转，具体递归过程如下：
如果root节点为null或者root没有左右子节点，则直接返回root；
否则，首先用temp暂存root的right子树，将root的right指向递归处理root的left子树后的结点，将root的left指向递归处理temp后的结点。
递归完成后即得到翻转后的二叉树。

import java.util.LinkedList;
import java.util.Queue;

public class LeetCode_226 {
    public static TreeNode invertTree(TreeNode root) {
        if (root == null || (root.left == null && root.right == null)) {
            return root;
        }
        TreeNode temp = root.right;
        root.right = invertTree(root.left);
        root.left = invertTree(temp);
        return root;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(4);
        root.left = new TreeNode(2);
        root.right = new TreeNode(7);
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(3);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(9);

        invertTree(root);
        Queue<TreeNode> nodes = new LinkedList<>();
        nodes.add(root);
        while (nodes.size() > 0) {
            TreeNode cur = nodes.poll();
            System.out.print(cur.val + " ");
            if (cur.left != null) {
                nodes.add(cur.left);
            }
            if (cur.right != null) {
                nodes.add(cur.right);
            }
        }
        for (TreeNode node : nodes) {
            System.out.print(node.val + " ");
        }
    }
}