current position:Home>Leetcode226 -- flip binary tree Java

Leetcode226 -- flip binary tree Java

2022-01-27 01:29:15 Co-King

Title Description :
 Insert picture description here
Ideas :

  • How to flip a binary tree ? In fact, it is to exchange the left and right child nodes of each node on the binary tree .
  • So how to do that ? In fact, it is to traverse all nodes of the binary tree , And then implement... For each node 【 Exchange child node 】 The operation of

Code implementation :

/** 1. Definition for a binary tree node. 2. public class TreeNode { 3. int val; 4. TreeNode left; 5. TreeNode right; 6. TreeNode() {} 7. TreeNode(int val) { this.val = val; } 8. TreeNode(int val, TreeNode left, TreeNode right) { 9. this.val = val; 10. this.left = left; 11. this.right = right; 12. } 13. } */
 //  How to flip a binary tree :  In fact, it is to exchange the left and right child nodes of each node on the binary tree ,
 //  So how to achieve it ?  That is to traverse all nodes of the binary tree , And implement the operation of switching child nodes for each node 
class Solution {
    
    public TreeNode invertTree(TreeNode root) {
    
        //  exit 
        if (root == null){
    
            return null;
        }
        //  The position of preorder traversal 
        //  about root node , You need to swap its left and right child nodes 
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;

        //  Recursive framework , Traverse and exchange all subtree nodes 
        invertTree(root.left);
        invertTree(root.right);
        //  Return to one root, In fact, it is the last binary tree to return 
        return root;
    }
}

summary :
There are two categories of binary tree algorithms :

  • Traversal binary tree type
    The point is that you only need to apply the recursive traversal framework of binary tree

  • Decompose subproblem types
    Is to clarify the definition of recursive function , Then use this definition

  • The binary tree traversal framework is these lines of code , Can traverse all nodes of the binary tree :
    The key is to decide which traversal framework the algorithm should use !!!

//  Binary tree traversal framework 
void traverse(TreeNode root) {
    
    //  The former sequence traversal 
    traverse(root.left)
    //  In the sequence traversal 
    traverse(root.right)
    //  After the sequence traversal 
}

copyright notice
author[Co-King],Please bring the original link to reprint, thank you.
https://en.cdmana.com/2022/01/202201270129095088.html

Random recommended