本文共 3220 字,大约阅读时间需要 10 分钟。
对称的二叉树
实现一个函数,用来判断一颗二叉树是不是对称的。注意,如果一个二叉树同此二叉树的镜像是同样的,定义其为对称的。/*public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; }}*/public class Solution { boolean isSymmetrical(TreeNode pRoot) { TreeNode node = getMirror(pRoot); return isSymmetrical(pRoot,node); } boolean isSymmetrical(TreeNode pRoot,TreeNode node) { if(pRoot == null && node == null){ return true; }else if(pRoot == null || node == null){ return false; } if(pRoot.val == node.val){ return isSymmetrical(pRoot.left,node.left)&&isSymmetrical(pRoot.right,node.right); } return false; } TreeNode getMirror(TreeNode pRoot){ if (pRoot == null) { return null; } TreeNode root = new TreeNode(pRoot.val); root.right = getMirror(pRoot.left); root.left = getMirror(pRoot.right); return root; }}
按之字形顺序打印二叉树
实现一个函数按照之字形打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右至左的顺序打印,第三行按照从左到右的顺序打印,其他行以此类推。import java.util.ArrayList;import java.util.*;/*public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; }}*/public class Solution { public ArrayList> Print(TreeNode pRoot) { ArrayList > aList=new ArrayList >(); if(pRoot==null) return aList; Stack s1=new Stack (); s1.add(pRoot); Stack s2=new Stack (); while(!s1.isEmpty()||!s2.isEmpty()){ if(!s1.isEmpty()){ ArrayList aList2=new ArrayList (); while(!s1.isEmpty()){ TreeNode p=s1.pop(); aList2.add(p.val); if(p.left!=null) s2.add(p.left); if(p.right!=null) s2.add(p.right); } aList.add(aList2); } else { ArrayList aList2=new ArrayList (); while(!s2.isEmpty()){ TreeNode p=s2.pop(); if(p.right!=null) s1.add(p.right); if(p.left!=null) s1.add(p.left); aList2.add(p.val); } aList.add(aList2); } } return aList; }}
序列化二叉树
实现两个函数,分别用来序列化和反序列化二叉树。/*public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; }}*/public class Solution { String Serialize(TreeNode root) { if(root == null) return ""; StringBuilder sb = new StringBuilder(); Serialize2(root, sb); return sb.toString(); } void Serialize2(TreeNode root, StringBuilder sb) { if(root == null) { sb.append("#,"); return; } sb.append(root.val); sb.append(','); Serialize2(root.left, sb); Serialize2(root.right, sb); } int index = -1; TreeNode Deserialize(String str) { if(str.length() == 0) return null; String[] strs = str.split(","); return Deserialize2(strs); } TreeNode Deserialize2(String[] strs) { index++; if(!strs[index].equals("#")) { TreeNode root = new TreeNode(0); root.val = Integer.parseInt(strs[index]); root.left = Deserialize2(strs); root.right = Deserialize2(strs); return root; } return null; }}
源代码:
转载地址:http://phrin.baihongyu.com/