This is the 27th day of my participation in the August More Text Challenge

Offer 55-i. Depth of binary tree

The title

Enter the root node of a binary tree to find the depth of the tree. The nodes (including root and leaf nodes) that pass from the root node to the leaf node form a path of the tree. The longest length of the path is the depth of the tree.

Such as:

Given a binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
Copy the code

Returns its maximum depth of 3.

Tip:

  1. The number of nodes is less than = 10000

Methods a

DFS: Maintain a global variable res. If the current traversal depth is greater than RES, update RES to the current depth.

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public int maxDepth(TreeNode root) { return dfs(root); } int dfs(TreeNode root) { if (root == null) return 0; return Math.max(dfs(root.left), dfs(root.right)) + 1; }}Copy the code

Method 2

BFS: sequence traversal

To traverse one layer of the binary tree each time, the total number of layers traversed is obtained, namely, the depth;

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public int maxDepth(TreeNode root) { LinkedList<TreeNode> q, t; q = new LinkedList<>(); if (root ! = null) q.add(root); int res = 0; while(q.size() > 0) { t = new LinkedList<>(); for (TreeNode node : q) { if (node.left ! = null) t.add(node.left); if (node.right ! = null) t.add(node.right); } res ++; q = t; } return res; }}Copy the code

Sword finger Offer 55-II. Balanced binary tree

The title

Input the root node of a binary tree to determine whether the tree is a balanced binary tree. A binary tree is a balanced binary tree if the depth difference between the left and right subtrees of any node is no more than 1.

Example 1:

Given a binary tree [3,9,20,null,null,15,7]

    3
   / \
  9  20
    /  \
   15   7
Copy the code

Returns true.

Example 2:

Given a binary tree [1,2,2,3,3,null,null,4,4]

       1
      / \
     2   2
    / \
   3   3
  / \
 4   4
Copy the code

Returns false.

Limitations:

  • 0 <= The number of nodes in the tree <= 10000

Methods a

DFS: Determine the difference between the left and right subtree heights of each node and update res. If res is greater than 1, false;

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { int res = 0; public boolean isBalanced(TreeNode root) { dfs(root); return res <= 1; } int dfs(TreeNode root) { if (root == null) return 0; int left = dfs(root.left); int right = dfs(root.right); res = Math.max(res, Math.abs(left - right)); return Math.max(left, right) + 1; }}Copy the code