算法:226. 翻转二叉树

[复制链接]
发表于 2024-6-8 04:09:47 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?立即注册

×
给你一棵二叉树的根节点 root ,翻转这棵二叉树,并返回其根节点。

示例 1:


  1. <strong>输入:</strong>root = [4,2,7,1,3,6,9]
  2. <strong>输出:</strong>[4,7,2,9,6,3,1]
复制代码
示例 2:


  1. <strong>输入:</strong>root = [2,1,3]
  2. <strong>输出:</strong>[2,3,1]
复制代码
示例 3:
  1. <strong>输入:</strong>root = []
  2. <strong>输出:</strong>[]
复制代码

提示:


  • 树中节点数目范围在 [0, 100] 内
  • -100 <= Node.val <= 100
方法一:递归法

  1. class Solution {
  2.     public TreeNode invertTree(TreeNode root) {
  3.         if (root == null) {
  4.             return null;
  5.         }
  6.         
  7.         // 递归翻转左右子树
  8.         TreeNode left = invertTree(root.left);
  9.         TreeNode right = invertTree(root.right);
  10.         
  11.         // 交换左右子树
  12.         root.left = right;
  13.         root.right = left;
  14.         
  15.         return root;
  16.     }
  17. }
复制代码
方法二:迭代法(使用栈) 

  1. import java.util.Stack;
  2. class Solution {
  3.     public TreeNode invertTree(TreeNode root) {
  4.         if (root == null) {
  5.             return null;
  6.         }
  7.         
  8.         Stack<TreeNode> stack = new Stack<>();
  9.         stack.push(root);
  10.         
  11.         while (!stack.isEmpty()) {
  12.             TreeNode node = stack.pop();
  13.             
  14.             // 交换左右子树
  15.             TreeNode temp = node.left;
  16.             node.left = node.right;
  17.             node.right = temp;
  18.             
  19.             // 将左右子树入栈
  20.             if (node.left != null) {
  21.                 stack.push(node.left);
  22.             }
  23.             if (node.right != null) {
  24.                 stack.push(node.right);
  25.             }
  26.         }
  27.         
  28.         return root;
  29.     }
  30. }
复制代码




免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!更多信息从访问主页:qidao123.com:ToB企服之家,中国第一个企服评测及商务社交产业平台。
继续阅读请点击广告
回复

使用道具 举报

×
登录参与点评抽奖,加入IT实名职场社区
去登录
快速回复 返回顶部 返回列表