提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其他

当前栏目

LeetCode笔记：226. Invert Binary Tree

笔记 对象
2023-03-15 23:23:57 时间

问题：

Invert a binary tree.

image.png to

image.png Trivia: 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.

大意：

反转一个二叉树。 从

image.png 到

image.png

琐事： Google表示如果你连反转二叉树都做不到就滚吧。

思路：

对于二叉树的每个子节点的左右节点都要反转，我们还是用递归，对每个节点都调用函数，这样就都可以反转了。就同置换变量的数字一样，我们可以创建两个新的节点对象，然后分别等同于其左右子节点，然后将其左节点变成其右节点的新对象，将其右节点变成其左节点的新对象，就可以了。同时我们对每个子节点都要进行同样的操作。还有一点很重要不要忘记了，我们一开始要先判断此节点是否为null，不为null才进行操作。

代码（Java）：

/**
 * Definition for a binary tree node.
 * public 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 null;
        } else {// 节点不为空
            TreeNode leftNode;// 左节点新对象
            TreeNode rightNode;// 右节点新对象
            if (root.left != null) {
                leftNode = invertTree(root.left);//对其子节点进行同样的操作，并赋给新对象
            } else {
                leftNode = null;
            }
            if (root.right != null) {
                rightNode = invertTree(root.right);//对其子节点进行同样的操作，并赋给新对象
            } else {
                rightNode = null;
            }
            // 反转左右子节点
            root.left = rightNode;
            root.right = leftNode;
            return root;
        }
    }
}

精简代码（Java）：

我们在处理其子节点时，也判断了是否是null的情况，但其实我们函数中对本节点就会进行一次判断，也就是说如果子节点为null，那么函数本身就会返回null，用不着特意处理了。所以可以精简一下：

/**
 * Definition for a binary tree node.
 * public 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 null;
        } else {
            TreeNode leftNode = invertTree(root.left);
            TreeNode rightNode = invertTree(root.right);
            root.left = rightNode;
            root.right = leftNode;
            return root;
        }
    }
}
// C++:
/**
 * Definition for a binary tree node.
 * 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;
        
        TreeNode* left = root->left;
        root->left = invertTree(root->right);
        root->right = invertTree(left);
        
        return root;
    }
};

合集：https://github.com/Cloudox/LeetCode-Record

查看作者首页

相关文章