leetcode 226. Invert Binary Tree 反转二叉树 + DFS深度优先搜索

梦里梦外; 2022-06-08 12:06 144阅读 0赞

Invert a binary tree.

4  
/ \\  
2 7  
/ \\ / \\  
1 3 6 9

4  
/ \\  
7 2  
/ \\ / \\  
9 6 3 1  
Trivia:  
This problem was inspired by this original tweet by Max Howell:  
Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.

这个就是最经典的反转二叉树的实现。

直接递归即可。

代码如下：

import java.util.ArrayList;
    import java.util.LinkedList;
    import java.util.List;
    import java.util.Queue;
    
    /*class TreeNode 
    {
         int val;
         TreeNode left;
         TreeNode right;
         TreeNode(int x) { val = x; }
    }*/
    
    
    /*
     * 这就是传说中牛逼哄哄的反转二叉树的问题
     * 递归解决即可
     * 假如是非递归解法，要注意这可能表示满二叉树
     * */
    public class Solution 
    {
        
        public TreeNode invertTree(TreeNode root) 
        {
            if(root==null)
                return root;
            invert(root);
            return root;        
        }
    
        public void invert(TreeNode root)
        {
            if(root!=null)
            {
                TreeNode tmp=root.left;
                root.left=root.right;
                root.right=tmp;
                invert(root.left);
                invert(root.right);
            }else
                return;
        }
    }

下面是C++的做法，就是一个简单的DFS深度优先遍历的简单应用

代码如下：

#include <iostream>
    #include <algorithm>
    #include <vector>
    #include <set>
    #include <map>
    
    using namespace std;
    
    /*
    struct TreeNode 
    {
         int val;
         TreeNode *left;
         TreeNode *right;
         TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };
    */
    
    class Solution
    {
    public:
        TreeNode* invertTree(TreeNode* root) 
        {
            if (root == NULL)
                return root;
            else
            {
                TreeNode* tmp = root->left;
                root->left = root->right;
                root->right = tmp;
                invertTree(root->left);
                invertTree(root->right);
                return root;
            }
        }
    };