Binary tree OJ questions (check whether two numbers are the same, subtree of another tree, flip binary tree, determine balanced binary tree, symmetric binary tree)

Article directory

  • Binary tree OJ question
    • 1. Check whether the two numbers are the same
      • 1. Ideas
      • 2. Problem solving steps
      • 3.Code
    • 2. A subtree of another tree
      • 1. Ideas
      • 2.Code
    • 3. Flip the binary tree
      • 1. Ideas
      • 2. Problem solving steps
      • 3.Code
    • 4. Judgment of Balanced Binary Tree
      • 1. Ideas
      • 2.Code
    • 5. Symmetric binary tree
      • 1. Ideas
      • 2.Code

Binary tree OJ question

1. Check whether the two numbers are the same

1. Idea

1. The two trees must have the same structure and the same node values.

2. One is empty and the other is not empty, with different structures. Both are empty and have the same structure. If both are not empty, determine whether the values are the same.

3. First determine whether the root nodes are the same

4. Then determine whether the left tree is the same, and then determine whether the right tree

2. Problem solving steps

  • 1. Determine whether the structures of two trees are the same
  • 2. If one node is empty and one node is not empty, it proves that the structure is inconsistent and returns false directly.
  • 3. If the structure is consistent, both are empty, or neither is empty. Neither is empty, including the same value and different value. If both are empty, false is returned.
  • 4. If neither is empty and the values are different, return true
  • 5. At this point, the situation of the root node has been judged. First recurse the left subtree. After the left subtree is judged, then recurse the right subtree for judgment.
  • 6. Finally return, the return values obtained from the two subtrees are ANDed, if false occurs, false is returned.
  • Time complexity: o(min(m,n))
  • Space complex: o (min(m,n))

3. Code

 //Determine whether two trees are the same
    public static boolean isSameTree(TreeNode p, TreeNode q) {<!-- -->
        if (p == null & amp; & amp; q != null || p != null & amp; & amp; q == null) {<!-- -->
            return false; // Ensure the structure is the same
        }//Either they are all empty, or they are not empty.
        if (p == null & amp; & amp; q == null) {<!-- -->
            return true;//The nodes are all empty and have the same structure
        }
        if (p.val != q.val) {<!-- -->
            return false;//If the structure is the same, the values must also be the same
        }
        //pq is not empty and the values of the root nodes are the same
        return isSameTree(p.left, q.left) & amp; & amp; isSameTree(p.right, q.right);
        //Recursively get the values returned from the left and right subtrees
    }

2. Subtree of another tree

1. Idea

0. You need to call the function you just wrote to determine whether two trees are the same.

1. Determine whether two trees are identical

2. If not the same, determine whether it is the same as the left subtree.

3. Then determine whether it is the same as the right subtree

4. If they are not the same, return false

5. Return false when root is equal to null to avoid null pointer exceptions.

2. Code

 //Determine whether two trees are the same
    public boolean isSameTree(TreeNode p, TreeNode q) {<!-- -->
        if (p == null & amp; & amp; q != null || p != null & amp; & amp; q == null) {<!-- -->
            return false; // Ensure the structure is the same
        }//Either they are all empty, or they are not empty.
        if (p == null & amp; & amp; q == null) {<!-- -->
            return true;//The nodes are all empty and have the same structure
        }
        if (p.val != q.val) {<!-- -->
            return false;//If the structure is the same, the values must also be the same
        }
        //pq is not empty and the values of the root nodes are the same
        return isSameTree(p.left, q.left) & amp; & amp; isSameTree(p.right, q.right);
        //Recursively get the values returned from the left and right subtrees
    }

    //Subtree of another tree
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {<!-- -->
        if (root == null){<!-- -->
            return false;//Avoid null pointer exception
        }

        if ( isSameTree(root,subRoot)){<!-- -->
            return true;//First determine whether the two trees are exactly the same
        }
        if (isSubtree(root.left,subRoot)){<!-- -->
            return true;//Determine whether it is the same as the left subtree
        }
        if (isSubtree(root.right,subRoot)){<!-- -->
            return true;//Determine whether it is the same as the right subtree
        }
        return false;//Not found, return false
    }
  • Time complexity: o (s * t)
  • Space complexity: o (Max (ds , dt ))

3. Flip the binary tree

1. Idea

1. Turn the whole tree over

2. First exchange the left subtree and right subtree of the root node

3. Then exchange the subtrees on the subtree

2. Problem solving steps

  • First determine whether the tree is empty
  • If not empty, use tmp to store the left child
  • Swap the left subtree and right subtree of the root node
  • First exchange the left and right subtrees in the left subtree, and then exchange the left and right subtrees in the right subtree.
  • Finally, the flip is completed and the root node is returned.

3. Code

 //Flip the binary tree
    public TreeNode invertTree(TreeNode root) {<!-- -->
        if (root == null){<!-- -->
            return null;
        }
        TreeNode tmp = root.left;//Exchange the left and right trees of the root node
        root.left = root.right;
        root.right = tmp;
        invertTree(root.left);//Exchange the subtrees in the left subtree
        invertTree(root.right);//Exchange the subtree in the right subtree
        return root;
    }

4. Judgment of Balanced Binary Tree

1. Idea

1. Each node must determine that the absolute value of the height difference between the left and right subtrees does not exceed 1. That is to say: | Height difference |<2

2.root is empty and returns true

3. The height difference between the left and right subtrees must be less than 2

4. The left and right subtrees must be balanced

2. Code

class Solution {<!-- -->
    //Judge balanced binary tree
    public boolean isBalanced(TreeNode root) {<!-- -->
        if (root == null) {<!-- -->
            return true; //If empty, return true
        }
        int leftHeight = maxDepth(root.left);//Get the height of the left subtree
        int rightHeight = maxDepth(root.right);//Get the height of the right subtree
        return Math.abs(leftHeight - rightHeight) < 2//The absolute value of the height difference between the left and right trees <2
                 & amp; & amp; isBalanced(root.left) & amp; & amp; isBalanced(root.right);
        //And it satisfies that both the left and right subtrees are balanced

    }
    public int maxDepth(TreeNode root){<!-- -->//Find height
        if(root == null){<!-- -->
            return 0;
        }
        int leftHeight = maxDepth(root.left);
        int rightHeight = maxDepth(root.right);
        return leftHeight>rightHeight?leftHeight + 1:rightHeight + 1;

    }
}
  • Time complexity: o (n2): Find the height of time complexity o(n). There are n nodes, so the time complexity is n2

How to change the time complexity to o(n)?

1. When finding the height of the left and right trees, the height of the subtree will be repeatedly found. The height of the subtree is the sum returned recursively.

2. When finding the height of a subtree, the subtree height of its subtree has already been calculated and repeated.

3. In other words, when calculating the height before, the height may have been unbalanced, but the maximum value + 1 was returned, and the absolute value of the degree difference < 2 was not considered.

4. Therefore, when you can find the height again, you can judge the height difference and return it directly if it is unbalanced to avoid repeated calculations.

 public boolean isBalanced(TreeNode root) {<!-- -->
        return maxDepth(root)>=0;//You only need to determine whether the returned value is >=0

    }
    public int maxDepth(TreeNode root){<!-- -->//Find height
        if(root == null){<!-- -->
            return 0;
        }
        int leftHeight = maxDepth(root.left);
        if(leftHeight<0){<!-- -->//If the left subtree returns a value of -1, it means there is an imbalance
            return -1;//No need to enter the right subtree, return directly
        }
        int rightHeight = maxDepth(root.right);
        if(rightHeight<0){<!-- -->//If -1 appears in the right subtree, return directly without performing subsequent operations.
            return -1;
        }
        if(Math.abs(leftHeight-rightHeight)<2){<!-- -->//Judge the height difference when finding the height
            return Math.max(leftHeight,rightHeight) + 1; //Conforms to return maximum value + 1
        }else {<!-- -->
            return -1;//return -1 if not met;
        }

    }
 }

After improvements, the time complexity has been reduced from o (n2) to o(n).

5. Symmetric binary tree

1. Idea

1. Determine whether the entire tree is axially symmetric -> determine whether the left subtree and right subtree are axially symmetrical

2. When the values of the root nodes are the same:

2. Determine whether the left tree of the left subtree and the right tree of the right subtree are symmetrical

3. Determine whether the right tree of the left subtree and the left tree of the right subtree are symmetrical

2. Code

 public boolean isSymmetric(TreeNode root) {<!-- -->
        if (root==null){<!-- -->
            return true;
        }
        return isSymmetricChild(root.left, root.right);
    }

    public boolean isSymmetricChild(TreeNode leftTree, TreeNode rightTree) {<!-- -->
        if (leftTree == null & amp; & amp; rightTree != null || leftTree != null & amp; & amp; rightTree == null) {<!-- -->
            return false;//Exclude situations where structures are inconsistent, and the rest are empty or none are empty.
        }
        if (leftTree == null & amp; & amp; rightTree == null) {<!-- -->
            return true;//The judgment is all empty.
        }
        if (leftTree.val != rightTree.val) {<!-- -->//After judging that the structures are consistent, don’t forget to judge whether the values are symmetrical
            return false;//When the structure is the same, determine whether the values of the left and right subtrees are the same
        }//At this time, the values are the same. Determine whether the left of the left tree and the right of the right tree are symmetrical, and whether the right of the left tree and the left of the right tree are symmetrical.
        return isSymmetricChild(leftTree.left, rightTree.right) & amp; & amp;
                isSymmetricChild(leftTree.right, rightTree.left);
    }

Click to move to the blog homepage, welcome~

Stealing cyk’s picture