[검지 Offer 학습] [문제 58: 대칭의 두 갈래 나무]

7286 단어 검지offer
제목: 두 갈래 나무가 대칭적인지 아닌지를 판단하는 함수를 실현하세요.만약 두 갈래 나무가 이 두 갈래 나무와 같은 거울이라면 대칭으로 정의하십시오.
사고방식: 귀속적인 방식으로 비교했다. 그리고 이곳의 대칭은 거울이 같다는 것이다.거울은 원래와 반대다.즉 왼쪽 나무의 왼쪽 나무는 오른쪽 나무의 오른쪽 나무와 같다.1. 결점이 비어 있을 때true로 돌아간다.2. 좌우 결점의 값을 비교한다. ① 대응하는 좌우 결점이 모두 비어 있을 때true로 돌아간다.② 대응하는 좌우 결점/하나가 비어 있고 하나가 비어 있지 않을 때 나무가 비대칭임을 설명하면false로 돌아간다.③ 좌우 결점에 대응하는 값이 같을 때 귀속을 사용하여 다음 결점을 판단한다.
프로그램:
class TreeNode{
	int val = 0;
	TreeNode left = null;
	TreeNode right = null;
	TreeNode(int val){
		this.val = val;
	}
}
public class subject58 {
	public static boolean isSymmetrical(TreeNode pRoot) {
		if(pRoot == null) {
			return true;
		}
		return isSymmetrical(pRoot, pRoot);
	}
	public static boolean isSymmetrical(TreeNode root1, TreeNode root2) {
	// 
		if(root1 == null && root2 == null) {// , true
			return true;
		}else if(root1 == null || root2 == null){// , , false
			return false;
		}else if(root1.val == root2.val){
			return isSymmetrical(root1.left, root2.right) && isSymmetrical(root1.right, root2.left);
		}
		return false;
	}
	public static void main(String args[]) {
		TreeNode root = new TreeNode(1);
		root.left = new TreeNode(2);
        root.right = new TreeNode(2);
        //root.left.left = new TreeNode(4);
        //root.left.right = new TreeNode(5);
        System.out.println(isSymmetrical(root));
	}
}

좋은 웹페이지 즐겨찾기