【Check 46】2024-04-08 - 226. 翻转二叉树

[larscheng]

226. 翻转二叉树

[larscheng]

思路

• 朴素递归：通过递归方法对每个节点进行左右子树的交换操作

• 递归栈：分解为处理左树和处理右树，通过递归栈对左树和右树进行交换 复杂度都为O(n),空间复杂度O(n)

  代码

  
  class Solution1 {
      //递归1次遍历，交换每个节点的左/右子节点位置，跳过叶子节点
      //O(n)/O(n)
      public TreeNode invertTree(TreeNode root) {
          invert(root);
          return root;
      }
  
      private void invert(TreeNode root) {
          if (root==null||(root.left==null&&root.right==null)){
              return;
          }
          TreeNode temp = root.left;
          root.left = root.right;
          root.right = temp;
  
          invert(root.left);
          invert(root.right);
      }
  }

```java
class Solution2 {
    //递归，分解问题，利用递归栈分别处理左右子树，最终处理根节点左右子树
    //O(n)/O(n)
    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;
    }
}

[larscheng]

思路

迭代 通过广度优先遍历，借助栈或者队列，记录每层节点，遍历栈或者队列内的节点，进行左右子树的节点交换操作

代码

class Solution {
    //迭代，广度优先遍历，队列记录每层的非叶子节点，遍历队列，进行交换左右子树
    //O(n)/O(n)
    public TreeNode invertTree(TreeNode root) {
        if (root==null){
            return null;
        }
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()){
            TreeNode temp = queue.poll();
            TreeNode left = temp.left;
            temp.left = temp.right;
            temp.right = left;

            if (temp.left!=null){
                queue.add(temp.left);
            }
            if (temp.right!=null){
                queue.add(temp.right);
            }
        }

        return root;
    }
}