[leetcode] 6. invert binary tree

Title Description

Description in English

Given the root of a binary tree, invert the tree, and return its root. Example 1:

​Input: root = [4,2,7,1,3,6,9] Output: [4,7,2,9,6,3,1] Example 2:

​Input: root = [2,1,3] Output: [2,3,1] Example 3: Input: root = [] Output: [] Constraints:

• The number of nodes in the tree is in the range [0, 100].

• -100 <= Node.val <= 100

English address

https://leetcode.com/problems/invert-binary-tree/

Description of Chinese version

Give you the root node of a binary tree root , Flip this binary tree , And return its root node .

Tips ：

• The number of nodes in the tree ranges from [0, 100] Inside

• -100 <= Node.val <= 100

Address of Chinese version

https://leetcode.cn/problems/invert-binary-tree/

Their thinking

Start at the root node , Exchange left and right subtrees （ Before looking at the answer , I am the default binary tree, and the non leaf nodes have left and right subtrees , But I tried several cases that never passed and found , Nodes that are not entered are used null Instead of ）, Then until the leaf node , Because the operation of the left and right subtrees in the middle exchange is the same , Consider recursive calls .

How to solve the problem

My version

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
     public TreeNode invertTree(TreeNode root) {
          if (root != null) {
            if (root.left != null) {
                if (root.right != null) {
                    TreeNode temp = root.left;
                    root.left = root.right;
                    root.right = temp;
                    invertTree(root.left);
                    invertTree(root.right);
                } else {
                    root.right = root.left;
                    root.left = null;
                    invertTree(root.right);
                }
            } else {
                root.left = root.right;
                root.right = null;
                invertTree(root.left);
            }
        }
        return root;
    }
}

Official edition

recursive

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    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;
    }
}

summary

As recorded in the problem-solving ideas , Before looking at the answer , I didn't expect the missing node to be used null Instead of , So use the root != null) && root.left != null&&root.right != null The judgment of the , If null And ignore , But I tried several times and failed , From these cases , You can use null Replace the missing node , So I made a modification . The official recursive method is also used , But in contrast, the efficiency is higher , The code is simpler .

Welcome students with better ideas to kick me in the comment area *〜(*≧ω≦)