欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

二叉树的深度(Java)

程序员文章站 2022-05-06 22:45:59
...

题目:

输入一棵二叉树的根结点,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。

二叉树的结点定义:

struct BinaryTreeNode{
    int m_nValue;
    BinaryTreeNode* m_pLeft;
    BinaryTreeNode* m_pRight;
};

树的结构体

public class TreeNode {
	int val = 0;
	TreeNode left = null;
	TreeNode right = null;

	public TreeNode(int val) {
		this.val = val;
	}
}

代码实现:利用递归

public static int treeDepth(TreeNode pRoot){
	if(pRoot == null){
		return 0;
	}
	int nLeft = treeDepth(pRoot.left);
	int nRight = treeDepth(pRoot.right);
	return (nLeft > nRight) ? (nLeft + 1) : (nRight + 1);
}

题目:

输入一棵二叉树的根结点,判断该树是不是平衡二叉树。如果某二叉树中任意结点的左右子树的深度相差不超过1,那么它就是一棵平衡二叉树。例如,下图中的二叉树就是一棵平衡二叉树。

二叉树的深度(Java)

代码实现:方法一:先序遍历

public static int treeDepth(TreeNode pRoot){
	if(pRoot == null){
		return 0;
	}
	int nLeft = treeDepth(pRoot.left);
	int nRight = treeDepth(pRoot.right);
	return (nLeft > nRight) ? nLeft + 1 : nRight + 1;
}

/**
 * 先序遍历判断会重复遍历子结点
 * @param pRoot
 * @return
 */
public static boolean isBalanced(TreeNode pRoot){
	if(pRoot == null){
		return true;
	}
	int left = treeDepth(pRoot.left);
	int right = treeDepth(pRoot.right);
	int diff = left - right;
	if(Math.abs(diff) > 1){
		return false;
	}
	return true;
}

方法二:后序遍历,每个结点只遍历了一次

public static boolean isBalanced1(TreeNode pRoot){
	int depth = 0;
	return isBalanced1(pRoot, depth);
}
public static boolean isBalanced1(TreeNode pRoot, int depth){
	if(pRoot == null){
		depth = 0;
		return true;
	}
	int left = 0, right = 0;
	if(isBalanced1(pRoot.left, left) && isBalanced1(pRoot, right)){
		int diff = left - right;
		if(Math.abs(diff) <= 1){
			depth = 1 + (left > right ? left : right);
			return true;
		}
	}
	return false;
}

 

相关标签: 二叉树的深度