LeetCode Invert Binary Tree 翻转二叉树

水深无声 2022-06-08 03:18 290阅读 0赞

题目描述：

Invert a binary tree.

样例输入输出：

  1. 1         1
  2.  / \       / \ 2   3  => 3   2
  3.    /       \   4         4

解法一：
递归实现

  1. private void invertRecursion(TreeNode root) {
  2.     if (root == null) {
  3.         return;
  4.     }
  5.     TreeNode tmp = root.left;
  6.     root.left = root.right;
  7.     root.right = tmp;
  8.     if (root.left != null) {
  9.         invertRecursion(root.left);
  10.     }
  11.     if (root.right != null) {
  12.         invertRecursion(root.right);
  13.     }
  14. }

解法二：
非递归实现 使用辅助空间

  1. private void invertLoop(TreeNode root) {
  2.    if (root == null) {
  3.         return;
  4.     }
  5.     Stack<TreeNode> stack = new Stack<>();
  6.     stack.push(root);
  7.     while (!stack.empty()) {
  8.         TreeNode tmp = stack.pop();
  9.         //交换左右子树
  10.         TreeNode l = tmp.left;
  11.         tmp.left = tmp.right;
  12.         tmp.right = l;
  13.         if (tmp.right != null) {
  14.             stack.push(tmp.right);
  15.         }
  16.         if (tmp.left != null) {
  17.             stack.push(tmp.left);
  18.         }
  19.     }
  20. }

发表评论

表情：
评论列表 （有 0 条评论，290人围观）

还没有评论，来说两句吧...

相关阅读