JAva対称のツリー
9811 ワード
1.対称の二叉木
1.タイトルの説明
二叉木が対称かどうかを判断するための関数を実装してください.なお、1つのツリーがこのツリーのミラーと同じである場合は、対称として定義されます.
2.問題の解き方
二叉木に積まれているかどうかは、類似の階層をたどって判断できます.まず、根ノードとその左右のサブツリー、左サブツリーの左サブツリーと右サブツリーの右サブツリーが同じで、左サブツリーの右サブツリーと右サブツリーの左サブツリーが同じであれば、再帰的にずっと判断します.
3.コード
実行:
1.タイトルの説明
二叉木が対称かどうかを判断するための関数を実装してください.なお、1つのツリーがこのツリーのミラーと同じである場合は、対称として定義されます.
2.問題の解き方
二叉木に積まれているかどうかは、類似の階層をたどって判断できます.まず、根ノードとその左右のサブツリー、左サブツリーの左サブツリーと右サブツリーの右サブツリーが同じで、左サブツリーの右サブツリーと右サブツリーの左サブツリーが同じであれば、再帰的にずっと判断します.
3.コード
public class isSymmetrical {
public static void main(String[] args) {
//
TreeNode root=new TreeNode(10);
TreeNode n1=new TreeNode(5);
TreeNode n2=new TreeNode(5);
TreeNode n3=new TreeNode(4);
TreeNode n4=new TreeNode(7);
TreeNode n5=new TreeNode(7);
TreeNode n6=new TreeNode(4);
//TreeNode n7=new TreeNode(19);
root.left=n1;
root.right=n2;
n1.left=n3;
n1.right=n4;
n2.left=n5;
n2.right=n6;
//n6.right=n7;
System.out.println(" :");
postOrderTraverse(root);
boolean temp=symmetrical(root);
System.out.println("
"+" :"+temp);
}
static boolean symmetrical(TreeNode pRoot)
{
if(pRoot == null){
return true;
}
return comRoot(pRoot.left, pRoot.right);
}
static boolean comRoot(TreeNode left, TreeNode right) {
if(left == null)
return right==null;
if(right == null)
return false;
if(left.val != right.val)
return false;
return comRoot(left.right, right.left) && comRoot(left.left, right.right);
}
//
public static void postOrderTraverse(TreeNode node) {
if (node == null)
return;
postOrderTraverse(node.left);
postOrderTraverse(node.right);
System.out.print(node.val + " ");
}
}
実行:
:
4 7 5 7 4 5 10
:true