剑指 Offer 27. 二叉树的镜像

题目

解题思路

递归法： 二叉树镜像定义： 对于二叉树中任意节点 root ，设其左 / 右子节点分别为 left, right ；则在二叉树的镜像中的对应 root 节点，其左 / 右子节点分别为 right, left。

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public TreeNode mirrorTree(TreeNode root) { if (root==null) return null; TreeNode tmp=root.left; root.left=mirrorTree(root.right); root.right=mirrorTree(tmp); return root; } } # Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def mirrorTree(self, root: TreeNode) -> TreeNode: if not root:return None tmp=root.left root.left=self.mirrorTree(root.right) root.right=self.mirrorTree(tmp) return root

剑指 Offer 28. 对称的二叉树

题目

解题思路

1.先镜像出一个新的树，与root树进行比较看是否相同（此时注意镜像函数中返回的一定得是一个新的树，而不是指向相同根节点的实际是一个树） 2.递归法

思路代码1

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public boolean isSymmetric(TreeNode root) { TreeNode newRoot=mirrorTree(root); if(newRoot==null) return true; return recur(newRoot.right,root.right); } public TreeNode mirrorTree(TreeNode root) { if (root==null) return null; //注意应该生成新的节点，而不是简单的指针变换 TreeNode node=new TreeNode(root.val); TreeNode tmp=root.right; node.right=mirrorTree(root.left); node.left=mirrorTree(tmp); return node; } boolean recur(TreeNode p,TreeNode q){ if (p == null && q == null) return true; else if (p == null || q == null) return false; return p.val == q.val && recur(p.left, q.left) && recur(p.right, q.right); } } # Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def isSymmetric(self, root: TreeNode) -> bool: #方法1 先镜像出一个新的树，与root树进行比较看是否相同 newRoot=self.mirrorTree(root) return self.recur(newRoot,root) def mirrorTree(self,root:TreeNode)-> TreeNode: if not root:return None node=TreeNode(root.val) node.left=self.mirrorTree(root.right) node.right=self.mirrorTree(root.left) return node def recur(self,p:TreeNode,q:TreeNode)->bool: if not p and not q : return True if not p or not q :return False return p.val==q.val and self.recur(p.left,q.left) and self.recur(p.right,q.right)

思路代码2

class Solution { public boolean isSymmetric(TreeNode root) { return root==null ? true :recur(root.left,root.right); } public boolean recur(TreeNode L,TreeNode R){ if(L==null&R==null) return true; else if (L==null||R==null) return false; return (L.val==R.val)&&recur(L.left,R.right)&&recur(L.right,R.left); } } class Solution: def isSymmetric(self, root: TreeNode) -> bool: #递归法，最简便 return True if not root else self.recur(root.left,root.right) def recur(self,L:TreeNode,R:TreeNode)->bool: if L is None and R is None :return True if L is None or R is None :return False return L.val==R.val and self.recur(L.left,R.right) and self.recur(L.right,R.left)