二叉树的深度

剑指offer面试题系列

题目

题目一：输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成一条路径，最长路径为树的深度。。

题目二：输入一棵树，判断该树是不是平衡树。结点的左右子树的高度差小于2为平衡树。

思路

此题需要用递归的思路来解析。

只需要在函数 treeDepth 的参数列表中传入当前所遍历到的深度 depth 即可。但是要注意：因为先遍历左子树，如果存在左子树，会造成 depth 加一，如果再将此参数传到遍历右子树的函数中，会再一次累加，结果错误。

所以本题中使用的方法就是：将未遍历任何子树前的深度保存在一个临时变量中 tmp。然后在遍历右子树时将此变量传入，则不会造成二次累加。

代码

package com.ans;
import java.util.ArrayList;

class TreeNode {
    public int data;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(int data) {
        this.data = data;
        left = right = null;
    }
}

class BinaryTree {

    // 根据数组创建二叉树
    public static TreeNode createBinaryTree(int[] arr) {
        ArrayList<TreeNode> NodeList = new ArrayList<TreeNode>();
        if (arr == null)
            return null;
        TreeNode root = new TreeNode(arr[0]);
        if (arr.length == 1)
            return root;
        for (int j = 0; j < arr.length; j++) {
            TreeNode newNode = new TreeNode(arr[j]);
            NodeList.add(newNode);
        }
        root = NodeList.get(0);
        for (int i = 0; i < arr.length / 2 - 1; i++) {
            NodeList.get(i).left = NodeList.get(2 * i + 1);
            NodeList.get(i).right = NodeList.get(2 * i + 2);
        }

        int lastIndex = arr.length / 2 - 1;
        NodeList.get(lastIndex).left = NodeList.get(2 * lastIndex + 1);
        if (arr.length % 2 == 1) {
            NodeList.get(lastIndex).right = NodeList.get(2 * lastIndex + 2);
        }

        return root;
    }

    // 计算二叉树的深度
    public static int treeDepth(TreeNode root, int depth) {
        if (root == null)
            return depth;
        if (root != null) {

            depth++;
            int tmp = depth;//记录当前树的长度
            if (root.left != null) {
                depth = treeDepth(root.left, depth);
            }
            if (root.right != null)
                tmp = treeDepth(root.right, tmp);
            if (tmp > depth)
                depth = tmp;
        }

        return depth;
    }

    // 先序遍历
    public static void preDisplay(TreeNode root) {
        if (root == null)
            return;
        System.out.print(root.data + " ");
        preDisplay(root.left);
        preDisplay(root.right);
    }
}

public class Solution7 {
    public static void main(String[] args) {
        int[] arr = { 1, 2, 3, 4, 5, 6};
        TreeNode root = BinaryTree.createBinaryTree(arr);
        BinaryTree.preDisplay(root);
        System.out.println("这颗二叉树的深度为：" + BinaryTree.treeDepth(root, 0));
    }
}

总结

题目二：思路与题目一思路大体一样，但是剑指offer上提到有更简单的算法，现在还没有想出来。。。

待续。。。