Skip to content

Latest commit

 

History

History
918 lines (795 loc) · 26.6 KB

0226.翻转二叉树.md

File metadata and controls

918 lines (795 loc) · 26.6 KB
Raw

参与本项目，贡献其他语言版本的代码，拥抱开源，让更多学习算法的小伙伴们收益！

226.翻转二叉树

力扣题目链接

翻转一棵二叉树。

226.翻转二叉树

这道题目背后有一个让程序员心酸的故事，听说 Homebrew的作者Max Howell，就是因为没在白板上写出翻转二叉树，最后被Google拒绝了。（真假不做判断，权当一个乐子哈）

题外话

这道题目是非常经典的题目，也是比较简单的题目（至少一看就会）。

但正是因为这道题太简单，一看就会，一些同学都没有抓住起本质，稀里糊涂的就把这道题目过了。

如果做过这道题的同学也建议认真看完，相信一定有所收获！

思路

《代码随想录》算法视频公开课：听说一位巨佬面Google被拒了，因为没写出翻转二叉树 | LeetCode：226.翻转二叉树，相信结合视频在看本篇题解，更有助于大家对本题的理解。

我们之前介绍的都是各种方式遍历二叉树，这次要翻转了，感觉还是有点懵逼。

这得怎么翻转呢？

如果要从整个树来看，翻转还真的挺复杂，整个树以中间分割线进行翻转，如图：

226.翻转二叉树1

可以发现想要翻转它，其实就把每一个节点的左右孩子交换一下就可以了。

关键在于遍历顺序，前中后序应该选哪一种遍历顺序？ （一些同学这道题都过了，但是不知道自己用的是什么顺序）

遍历的过程中去翻转每一个节点的左右孩子就可以达到整体翻转的效果。

注意只要把每一个节点的左右孩子翻转一下，就可以达到整体翻转的效果

这道题目使用前序遍历和后序遍历都可以，唯独中序遍历不方便，因为中序遍历会把某些节点的左右孩子翻转了两次！建议拿纸画一画，就理解了

那么层序遍历可以不可以呢？依然可以的！只要把每一个节点的左右孩子翻转一下的遍历方式都是可以的！

递归法

对于二叉树的递归法的前中后序遍历，已经在二叉树：前中后序递归遍历详细讲解了。

我们下文以前序遍历为例，通过动画来看一下翻转的过程:

翻转二叉树

我们来看一下递归三部曲：

  1. 确定递归函数的参数和返回值

参数就是要传入节点的指针，不需要其他参数了，通常此时定下来主要参数，如果在写递归的逻辑中发现还需要其他参数的时候，随时补充。

返回值的话其实也不需要，但是题目中给出的要返回root节点的指针，可以直接使用题目定义好的函数，所以就函数的返回类型为TreeNode*。

TreeNode* invertTree(TreeNode* root)
  1. 确定终止条件

当前节点为空的时候，就返回

if (root == NULL) return root;
  1. 确定单层递归的逻辑

因为是先前序遍历，所以先进行交换左右孩子节点，然后反转左子树，反转右子树。

swap(root->left, root->right);
invertTree(root->left);
invertTree(root->right);

基于这递归三步法，代码基本写完，C++代码如下：

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == NULL) return root;
        swap(root->left, root->right);  // 中
        invertTree(root->left);         // 左
        invertTree(root->right);        // 右
        return root;
    }
};

迭代法

深度优先遍历

二叉树：听说递归能做的，栈也能做！中给出了前中后序迭代方式的写法，所以本题可以很轻松的写出如下迭代法的代码：

C++代码迭代法（前序遍历）

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == NULL) return root;
        stack<TreeNode*> st;
        st.push(root);
        while(!st.empty()) {
            TreeNode* node = st.top();              // 中
            st.pop();
            swap(node->left, node->right);
            if(node->right) st.push(node->right);   // 右
            if(node->left) st.push(node->left);     // 左
        }
        return root;
    }
};

如果这个代码看不懂的话可以再回顾一下二叉树：听说递归能做的，栈也能做！。

我们在二叉树：前中后序迭代方式的统一写法中介绍了统一的写法，所以，本题也只需将文中的代码少做修改便可。

C++代码如下迭代法（前序遍历）

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        stack<TreeNode*> st;
        if (root != NULL) st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top();
            if (node != NULL) {
                st.pop();
                if (node->right) st.push(node->right);  // 右
                if (node->left) st.push(node->left);    // 左
                st.push(node);                          // 中
                st.push(NULL);
            } else {
                st.pop();
                node = st.top();
                st.pop();
                swap(node->left, node->right);          // 节点处理逻辑
            }
        }
        return root;
    }
};

如果上面这个代码看不懂，回顾一下文章二叉树：前中后序迭代方式的统一写法。

广度优先遍历

也就是层序遍历，层数遍历也是可以翻转这棵树的，因为层序遍历也可以把每个节点的左右孩子都翻转一遍，代码如下：

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        queue<TreeNode*> que;
        if (root != NULL) que.push(root);
        while (!que.empty()) {
            int size = que.size();
            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                swap(node->left, node->right); // 节点处理
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
        }
        return root;
    }
};

如果对以上代码不理解，或者不清楚二叉树的层序遍历，可以看这篇二叉树：层序遍历登场！

拓展

文中我指的是递归的中序遍历是不行的，因为使用递归的中序遍历，某些节点的左右孩子会翻转两次。

如果非要使用递归中序的方式写，也可以，如下代码就可以避免节点左右孩子翻转两次的情况：

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == NULL) return root;
        invertTree(root->left);         // 左
        swap(root->left, root->right);  // 中
        invertTree(root->left);         // 注意 这里依然要遍历左孩子，因为中间节点已经翻转了
        return root;
    }
};

代码虽然可以，但这毕竟不是真正的递归中序遍历了。

但使用迭代方式统一写法的中序是可以的。

代码如下：

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        stack<TreeNode*> st;
        if (root != NULL) st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top();
            if (node != NULL) {
                st.pop();
                if (node->right) st.push(node->right);  // 右
                st.push(node);                          // 中
                st.push(NULL);
                if (node->left) st.push(node->left);    // 左

            } else {
                st.pop();
                node = st.top();
                st.pop();
                swap(node->left, node->right);          // 节点处理逻辑
            }
        }
        return root;
    }
};

为什么这个中序就是可以的呢，因为这是用栈来遍历，而不是靠指针来遍历，避免了递归法中翻转了两次的情况，大家可以画图理解一下，这里有点意思的。

总结

针对二叉树的问题，解题之前一定要想清楚究竟是前中后序遍历，还是层序遍历。

二叉树解题的大忌就是自己稀里糊涂的过了（因为这道题相对简单），但是也不知道自己是怎么遍历的。

这也是造成了二叉树的题目“一看就会，一写就废”的原因。

针对翻转二叉树，我给出了一种递归，三种迭代（两种模拟深度优先遍历，一种层序遍历）的写法，都是之前我们讲过的写法，融汇贯通一下而已。

大家一定也有自己的解法，但一定要成方法论，这样才能通用，才能举一反三！

其他语言版本

Java

//DFS递归
class Solution {
   /**
     * 前后序遍历都可以
     * 中序不行，因为先左孩子交换孩子，再根交换孩子（做完后，右孩子已经变成了原来的左孩子），再右孩子交换孩子（此时其实是对原来的左孩子做交换）
     */
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        invertTree(root.left);
        invertTree(root.right);
        swapChildren(root);
        return root;
    }

    private void swapChildren(TreeNode root) {
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
    }
}

//BFS
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {return null;}
        ArrayDeque<TreeNode> deque = new ArrayDeque<>();
        deque.offer(root);
        while (!deque.isEmpty()) {
            int size = deque.size();
            while (size-- > 0) {
                TreeNode node = deque.poll();
                swap(node);
                if (node.left != null) deque.offer(node.left);
                if (node.right != null) deque.offer(node.right);
            }
        }
        return root;
    }

    public void swap(TreeNode root) {
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
    }
}

Python

递归法：前序遍历：

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if not root:
            return None
        root.left, root.right = root.right, root.left #中
        self.invertTree(root.left) #左
        self.invertTree(root.right) #右
        return root

递归法：后序遍历：

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if root is None:
            return None
        self.invertTree(root.left)
        self.invertTree(root.right)
        root.left, root.right = root.right, root.left
        return root

迭代法：深度优先遍历（前序遍历）：

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if not root:
            return root
        st = []
        st.append(root)
        while st:
            node = st.pop()
            node.left, node.right = node.right, node.left #中
            if node.right:
                st.append(node.right) #右
            if node.left:
                st.append(node.left) #左
        return root

迭代法：广度优先遍历（层序遍历）：

import collections
class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        queue = collections.deque() #使用deque()
        if root:
            queue.append(root)
        while queue:
            size = len(queue)
            for i in range(size):
                node = queue.popleft()
                node.left, node.right = node.right, node.left #节点处理
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        return root

迭代法：广度优先遍历（层序遍历），和之前的层序遍历写法一致：

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root: return root
        from collections import deque
        que=deque([root])    
        while que:
            size=len(que)
            for i in range(size):
                cur=que.popleft()
                cur.left, cur.right = cur.right, cur.left
                if cur.left: que.append(cur.left)
                if cur.right: que.append(cur.right)
        return root

Go

递归版本的前序遍历

func invertTree(root *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }
    root.Left, root.Right = root.Right, root.Left    //交换
    
    invertTree(root.Left)
    invertTree(root.Right)

    return root
}

递归版本的后序遍历

func invertTree(root *TreeNode) *TreeNode {
    if root == nil {
        return root
    }
    
    invertTree(root.Left)     //遍历左节点
    invertTree(root.Right)    //遍历右节点
    root.Left, root.Right = root.Right, root.Left    //交换
    
    return root
}

迭代版本的前序遍历

func invertTree(root *TreeNode) *TreeNode {
    stack := []*TreeNode{}
    node := root
    for node != nil || len(stack) > 0 {
        for node != nil {
            node.Left, node.Right = node.Right, node.Left    //交换
            stack = append(stack,node)
            node = node.Left
        }
        node = stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        node = node.Right
    }
    
    return root
}

迭代版本的后序遍历

func invertTree(root *TreeNode) *TreeNode {
    stack := []*TreeNode{}
    node := root
    var prev *TreeNode
    for node != nil || len(stack) > 0 {
        for node != nil {
            stack = append(stack, node)
            node = node.Left
        }
        node = stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        if node.Right == nil || node.Right == prev {
            node.Left, node.Right = node.Right, node.Left     //交换
            prev = node
            node = nil
        } else {
            stack = append(stack, node)
            node = node.Right
        }
    }
    
    return root
}

层序遍历

func invertTree(root *TreeNode) *TreeNode {
    if root == nil{
        return root
    }
    queue := list.New()
    node := root
    queue.PushBack(node)
    for queue.Len() > 0 {
        length := queue.Len()
        for i := 0; i < length; i++ {
            e := queue.Remove(queue.Front()).(*TreeNode)
            e.Left, e.Right = e.Right, e.Left    //交换
            if e.Left != nil {
                queue.PushBack(e.Left)
            }
            if e.Right != nil {
                queue.PushBack(e.Right)
            }
        }
    }
    return root
}

JavaScript

使用递归版本的前序遍历

var invertTree = function(root) {
    // 终止条件
    if (!root) {
        return null;
    }
    // 交换左右节点
    const rightNode = root.right;
    root.right = invertTree(root.left);
    root.left = invertTree(rightNode);
    return root;
};

使用迭代版本(统一模板))的前序遍历：

var invertTree = function(root) {
    //我们先定义节点交换函数
    const invertNode = function(root, left, right) {
        let temp = left;
        left = right;
        right = temp;
        root.left = left;
        root.right = right;
    }
    //使用迭代方法的前序遍历 
    let stack = [];
    if(root === null) {
        return root;
    }
    stack.push(root);
    while(stack.length) {
        let node = stack.pop();
        if(node !== null) {
            //前序遍历顺序中左右  入栈顺序是前序遍历的倒序右左中
            node.right && stack.push(node.right);
            node.left && stack.push(node.left);
            stack.push(node);
            stack.push(null);
        } else {
            node = stack.pop();
            //节点处理逻辑
            invertNode(node, node.left, node.right);
        }
    }
    return root;
};

使用层序遍历：

var invertTree = function(root) {
    //我们先定义节点交换函数
    const invertNode = function(root, left, right) {
        let temp = left;
        left = right;
        right = temp;
        root.left = left;
        root.right = right;
    }
    //使用层序遍历
    let queue = [];
    if(root === null) {
        return root;
    } 
    queue.push(root);
    while(queue.length) {
        let length = queue.length;
        while(length--) {
            let node = queue.shift();
            //节点处理逻辑
            invertNode(node, node.left, node.right);
            node.left && queue.push(node.left);
            node.right && queue.push(node.right);
        }
    }
    return root;
};

TypeScript：

递归法：

// 递归法（前序遍历）
function invertTree(root: TreeNode | null): TreeNode | null {
    if (root === null) return root;
    let tempNode: TreeNode | null = root.left;
    root.left = root.right;
    root.right = tempNode;
    invertTree(root.left);
    invertTree(root.right);
    return root;
};

// 递归法（后序遍历）
function invertTree(root: TreeNode | null): TreeNode | null {
    if (root === null) return root;
    invertTree(root.left);
    invertTree(root.right);
    let tempNode: TreeNode | null = root.left;
    root.left = root.right;
    root.right = tempNode;
    return root;
};

// 递归法（中序遍历）
function invertTree(root: TreeNode | null): TreeNode | null {
    if (root === null) return root;
    invertTree(root.left);
    let tempNode: TreeNode | null = root.left;
    root.left = root.right;
    root.right = tempNode;
    // 因为左右节点已经进行交换，此时的root.left 是原先的root.right
    invertTree(root.left);
    return root;
};

迭代法：

// 迭代法（栈模拟前序遍历）
function invertTree(root: TreeNode | null): TreeNode | null {
    let helperStack: TreeNode[] = [];
    let curNode: TreeNode,
        tempNode: TreeNode | null;
    if (root !== null) helperStack.push(root);
    while (helperStack.length > 0) {
        curNode = helperStack.pop()!;
        // 入栈操作最好在交换节点之前进行，便于理解
        if (curNode.right) helperStack.push(curNode.right);
        if (curNode.left) helperStack.push(curNode.left);
        tempNode = curNode.left;
        curNode.left = curNode.right;
        curNode.right = tempNode;
    }
    return root;
};

// 迭代法（栈模拟中序遍历-统一写法形式）
function invertTree(root: TreeNode | null): TreeNode | null {
    let helperStack: (TreeNode | null)[] = [];
    let curNode: TreeNode | null,
        tempNode: TreeNode | null;
    if (root !== null) helperStack.push(root);
    while (helperStack.length > 0) {
        curNode = helperStack.pop();
        if (curNode !== null) {
            if (curNode.right !== null) helperStack.push(curNode.right);
            helperStack.push(curNode);
            helperStack.push(null);
            if (curNode.left !== null) helperStack.push(curNode.left);
        } else {
            curNode = helperStack.pop()!;
            tempNode = curNode.left;
            curNode.left = curNode.right;
            curNode.right = tempNode;
        }
    }
    return root;
};

// 迭代法（栈模拟后序遍历-统一写法形式）
function invertTree(root: TreeNode | null): TreeNode | null {
    let helperStack: (TreeNode | null)[] = [];
    let curNode: TreeNode | null,
        tempNode: TreeNode | null;
    if (root !== null) helperStack.push(root);
    while (helperStack.length > 0) {
        curNode = helperStack.pop();
        if (curNode !== null) {
            helperStack.push(curNode);
            helperStack.push(null);
            if (curNode.right !== null) helperStack.push(curNode.right);
            if (curNode.left !== null) helperStack.push(curNode.left);
        } else {
            curNode = helperStack.pop()!;
            tempNode = curNode.left;
            curNode.left = curNode.right;
            curNode.right = tempNode;
        }
    }
    return root;
};

// 迭代法（队列模拟层序遍历）
function invertTree(root: TreeNode | null): TreeNode | null {
    const helperQueue: TreeNode[] = [];
    let curNode: TreeNode,
        tempNode: TreeNode | null;
    if (root !== null) helperQueue.push(root);
    while (helperQueue.length > 0) {
        for (let i = 0, length = helperQueue.length; i < length; i++) {
            curNode = helperQueue.shift()!;
            tempNode = curNode.left;
            curNode.left = curNode.right;
            curNode.right = tempNode;
            if (curNode.left !== null) helperQueue.push(curNode.left);
            if (curNode.right !== null) helperQueue.push(curNode.right);
        }
    }
    return root;
};

C

递归法

struct TreeNode* invertTree(struct TreeNode* root){
    if(!root)
        return NULL;
    //交换结点的左右孩子（中）
    struct TreeNode* temp = root->right;
    root->right = root->left;
    root->left = temp;
    左
    invertTree(root->left);
    //右
    invertTree(root->right);
    return root;
}

迭代法：深度优先遍历

struct TreeNode* invertTree(struct TreeNode* root){
    if(!root)
        return NULL;
    //存储结点的栈
    struct TreeNode** stack = (struct TreeNode**)malloc(sizeof(struct TreeNode*) * 100);
    int stackTop = 0;
    //将根节点入栈
    stack[stackTop++] = root;
    //若栈中还有元素（进行循环）
    while(stackTop) {
        //取出栈顶元素
        struct TreeNode* temp = stack[--stackTop];
        //交换结点的左右孩子
        struct TreeNode* tempNode = temp->right;
        temp->right = temp->left;
        temp->left = tempNode;
        //若当前结点有左右孩子，将其入栈
        if(temp->right)
            stack[stackTop++] = temp->right;
        if(temp->left)
            stack[stackTop++] = temp->left;
    }
    return root;
}

Swift：

// 前序遍历-递归
func invertTree(_ root: TreeNode?) -> TreeNode? {
    guard let root = root else {
        return root
    }
    let tmp = root.left
    root.left = root.right
    root.right = tmp
    let _ = invertTree(root.left)
    let _ = invertTree(root.right)
    return root
}

// 层序遍历-迭代
func invertTree1(_ root: TreeNode?) -> TreeNode? {
    guard let root = root else {
        return nil
    }
    var queue = [TreeNode]()
    queue.append(root)
    while !queue.isEmpty {
        let node = queue.removeFirst()
        let tmp = node.left
        node.left = node.right
        node.right = tmp
        if let left = node.left {
            queue.append(left)
        }
        if let right = node.right {
            queue.append(right)
        }
    }
    return root
}

深度优先递归。

func invertTree(_ root: TreeNode?) -> TreeNode? {
    guard let node = root else { return root }
    swap(&node.left, &node.right)
    _ = invertTree(node.left)
    _ = invertTree(node.right)
    return root
}

深度优先迭代，子结点顺序不重要，从根结点出发深度遍历即可。

func invertTree(_ root: TreeNode?) -> TreeNode? {
    guard let node = root else { return root }
    var stack = [node]
    while !stack.isEmpty {
        guard let node = stack.popLast() else { break }
        swap(&node.left, &node.right)
        if let node = node.left { stack.append(node) }
        if let node = node.right { stack.append(node) }
    }
    return root
}

广度优先迭代。

func invertTree(_ root: TreeNode?) -> TreeNode? {
    guard let node = root else { return root }
    var queue = [node]
    while !queue.isEmpty {
        let count = queue.count
        for _ in 0 ..< count {
            let node = queue.removeFirst()
            swap(&node.left, &node.right)
            if let node = node.left { queue.append(node) }
            if let node = node.right { queue.append(node) }
        }
    }
    return root
}

深度优先遍历（前序遍历）:

object Solution {
  def invertTree(root: TreeNode): TreeNode = {
    if (root == null) return root
    // 递归
    def process(node: TreeNode): Unit = {
      if (node == null) return
      // 翻转节点
      val curNode = node.left
      node.left = node.right
      node.right = curNode
      process(node.left)
      process(node.right)
    }
    process(root)
    root
  }
}

广度优先遍历（层序遍历）:

object Solution {
  import scala.collection.mutable
  def invertTree(root: TreeNode): TreeNode = {
    if (root == null) return root
    val queue = mutable.Queue[TreeNode]()
    queue.enqueue(root)
    while (!queue.isEmpty) {
      val len = queue.size
      for (i <- 0 until len) {
        var curNode = queue.dequeue()
        if (curNode.left != null) queue.enqueue(curNode.left)
        if (curNode.right != null) queue.enqueue(curNode.right)
        // 翻转
        var tmpNode = curNode.left
        curNode.left = curNode.right
        curNode.right = tmpNode
      }
    }
    root
  }
}

rust

impl Solution {
    //* 递归 */
    pub fn invert_tree(root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
        if let Some(node) = root.as_ref() {
            let (left, right) = (node.borrow().left.clone(), node.borrow().right.clone());
            node.borrow_mut().left = Self::invert_tree(right);
            node.borrow_mut().right = Self::invert_tree(left);
        }
        root
    }
    //* 迭代 */
    pub fn invert_tree(root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
        let mut stack = vec![root.clone()];
        while !stack.is_empty() {
            if let Some(node) = stack.pop().unwrap() {
                let (left, right) = (node.borrow().left.clone(), node.borrow().right.clone());
                stack.push(right.clone());
                stack.push(left.clone());
                node.borrow_mut().left = right;
                node.borrow_mut().right = left;
            }
        }
        root
    }
}