题目一:
输入一棵二叉树,,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。
32 3-1 -1-1 -1样例输出:2
题目二:
输入一棵二叉树的根节点,判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1,那么它就是一棵平衡二叉树。
题目一解法:
二叉树的深度是其左右子树深度的较大值加1.递归求解。
#include<stdio.h>int a[20][2];int TreeDepth(int i,int n){if (i==-1){return 0;}int ldep =0;if (a[i-1][0]!=-1){ldep = TreeDepth(a[i-1][0],n);}int rdep =0;if (a[i-1][1]!=-1){rdep = TreeDepth(a[i-1][1],n);}return ldep>rdep?ldep+1:rdep+1;}int main(){int n;while(~scanf("%d",&n)){int i;for (i=0;i<n;i++){scanf("%d%d",&a[i][0],&a[i][1]);}int depth = TreeDepth(1,n);printf("%d\n",depth);}return 0;}
题目二解法一:
递归求解
bool IsBalanced(BinaryTreeNode *root) { if(root==NULL)return true;int left=TreeDepth(root->left); int right=TreeDepth(root->right); int diff = left-right;if(diff>1 || diff <-1)return false;return IsBalanced(root->left)&&IsBalanced(root->right); }
题目二解法二:
解法一由于一个节点会被重复遍历多次,效率低。
后序遍历二叉树的每个节点,在遍历到一个节点之前我们就已经遍历了他的左右子树。边遍历边判断每个节点是不是平衡的。
public boolean isBalanced(BinaryTreeNode root){int depth=0;return isBalanced(root,depth);}public boolean isBalanced(BinaryTreeNode root,int depth){if(root==null){depth=0;return true;}int left=0,right=0;if(isBalanced(root.lefNode, left)&&isBalanced(root.rightNode,right)){int diff=left-right;if(diff<=1 && diff>=-1){depth=1+(left>right?left:right);return true;}}return false;}
夫妇一条心,泥土变黄金。