1、常见二叉树数据结构如下：

1
2
3
4
5
6
7
8
9
10
/*
 * Definition for a binary tree node.
 */
 
 struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

2、二叉树的深度

可以使用递归算法分别求出左子树和右子树的深度，两个深度的较大值 +1 即可。代码如下：

1
2
3
4
5
6
7
8
9
public static int getMaxDepth(TreeNode root) {
          if (root == null)
              return 0;
          else {
              int left = getMaxDepth(root.left);
              int right = getMaxDepth(root.right);
              return 1 + Math.max(left, right);
          }
     }

3、二叉树广度

求二叉树的广度需要使用队列，层次遍历二叉树。在上一层遍历完成后，下一层的所有节点已经放到队列中，此时队列中的元素个数就是下一层的宽度。以此类推，依次遍历下一层即可求出二叉树的最大宽度。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public static int getMaxWidth(TreeNode root) {
    if (root == null)
         return 0;
 
    Queue<TreeNode> queue = new ArrayDeque<TreeNode>();
    int maxWitdth = 1; // 最大宽度
    queue.add(root); // 入队
 
    while (true)
    {
         int len = queue.size(); // 当前层的节点个数           
         if (len == 0)
              break;
         while (len > 0)
         {                // 如果当前层，还有节点
             TreeNode t = queue.poll();
             len--;
             if (t.left != null)
                 queue.add(t.left); // 下一层节点入队
             if (t.right != null)
                 queue.add(t.right);// 下一层节点入队
          }
          maxWitdth = Math.max(maxWitdth, queue.size());
     }
     return maxWitdth;
 }