【每日一题-leetcode】226.翻转二叉树

226.翻转二叉树

226. 翻转二叉树

难度简单413

翻转一棵二叉树。

示例：

输入：

     4
   /   
  2     7
 /    / 
1   3 6   9

输出：

     4
   /   
  7     2
 /    / 
9   6 3   1

1.DFS

time : O(n)

space: O(n) 最好 O(1) 最坏 O(n)退换成链表

  //1.递归  DFS
        public TreeNode invertTree(TreeNode root) {
            if(root == null)    return null;
            TreeNode tmp = root.left;  
            root.left = invertTree(root.right);  
            root.right = invertTree(tmp);
            return root;
        }

2.栈

time：O(n)

space：O(n)

   //栈
        public TreeNode invertTree(TreeNode root) {
            if(root == null) return null;
            Stack<TreeNode> stack = new Stack<>();
            stack.push(root);
            while(!stack.isEmpty()){
                TreeNode t = stack.pop();
                if(t.left != null) stack.push(t.left);
                if(t.right != null) stack.push(t.right);
                TreeNode tmp = t.left;
                t.left = t.right;
                t.right = tmp;  
            }
            return root;
        }