58、对称二叉树
/*思路：首先根节点以及其左右子树，左子树的左子树和右子树的右子树相同 * 左子树的右子树和右子树的左子树相同即可，采用递归 * 非递归也可，采用栈或队列存取各级子树根节点 */ /* 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) { if(pRoot==null){ return true; } return isSymmetrical(pRoot.left,pRoot.right); } public boolean isSymmetrical(TreeNode left,TreeNode right){ if(left==null&&right==null){ return true; } if(left==null||right==null){ return false; } return left.val==right.val&&(isSymmetrical(left.left,right.right))&&(isSymmetrical(left.right,right.left)); } }
非递归方法：
DFS使用stack来保存成对的节点
1.出栈的时候也是成对成对的 ，
1.若都为空，继续；
2.一个为空，返回false;
3.不为空，比较当前值，值不等，返回false；
2.确定入栈顺序，每次入栈都是成对成对的，如left.left， right.right ;left.rigth,right.left
*/
boolean isSymmetricalDFS(TreeNode pRoot) { if(pRoot == null) return true; Stack<TreeNode> s = new Stack<>(); s.push(pRoot.left); s.push(pRoot.right); while(!s.empty()) { TreeNode right = s.pop();//成对取出 TreeNode left = s.pop(); if(left == null && right == null) continue; if(left == null || right == null) return false; if(left.val != right.val) return false; //成对插入 s.push(left.left); s.push(right.right); s.push(left.right); s.push(right.left); } return true; }
59、按之字形书序打印二叉树
超级好用的Collections.reverse方法
import java.util.ArrayList; import java.util.Collections; /* public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */ import java.util.Queue; import java.util.LinkedList; public class Solution { public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) { ArrayList<ArrayList<Integer>> listAll=new ArrayList<ArrayList<Integer>>(); Queue<TreeNode> queue=new LinkedList<TreeNode>(); boolean flag=true; if(pRoot==null){ return listAll; } queue.add(pRoot); while(!queue.isEmpty()){ int size=queue.size(); ArrayList<Integer> list=new ArrayList<Integer>(); for(int i=0;i<size;i++){ TreeNode node=queue.remove(); list.add(node.val); if(node.left!=null){ queue.add(node.left); } if(node.right!=null){ queue.add(node.right); } } if(list!=null){ if(flag){ listAll.add(list); }else{ Collections.reverse(list); listAll.add(list); } } flag=!flag; } return listAll; } }
///两个栈的方法
public static ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) { int layer = 1; //s1存奇数层节点 Stack<TreeNode> s1 = new Stack<TreeNode>(); s1.push(pRoot); //s2存偶数层节点 Stack<TreeNode> s2 = new Stack<TreeNode>(); ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>(); while (!s1.empty() || !s2.empty()) { if (layer%2 != 0) { ArrayList<Integer> temp = new ArrayList<Integer>(); while (!s1.empty()) { TreeNode node = s1.pop(); if(node != null) { temp.add(node.val); System.out.print(node.val + " "); s2.push(node.left); s2.push(node.right); } } if (!temp.isEmpty()) { list.add(temp); layer++; System.out.println(); } } else { ArrayList<Integer> temp = new ArrayList<Integer>(); while (!s2.empty()) { TreeNode node = s2.pop(); if(node != null) { temp.add(node.val); System.out.print(node.val + " "); s1.push(node.right); s1.push(node.left); } } if (!temp.isEmpty()) { list.add(temp); layer++; System.out.println(); } } } return list; }
60、把二叉树打印成多行
其实就是一个层次遍历，用队列+totalCount
import java.util.ArrayList; import java.util.Stack; /* public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */ public class Solution { ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) { ArrayList<ArrayList<Integer>> list=new ArrayList<ArrayList<Integer>>(); Stack<TreeNode> stack=new Stack<TreeNode>(); stack.push(pRoot); int count=0; int totalCount=1; ArrayList<Integer> temp=new ArrayList<Integer>(); while(!stack.isEmpty()){ TreeNode node=stack.pop(); count++; if(node!=null){ temp.add(node.val); if(node.right!=null) stack.push(node.right); if(node.left!=null) stack.push(node.left); } if(count==totalCount){ count=0; totalCount=stack.size(); list.add(temp); temp=new ArrayList<Integer>(); } } return list; } }
61、序列化二叉树
/* public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */ public class Solution { public int index = -1; String Serialize(TreeNode root) { StringBuffer sb = new StringBuffer(); if(root == null){ sb.append("#,"); return sb.toString(); } sb.append(root.val + ","); sb.append(Serialize(root.left)); sb.append(Serialize(root.right)); return sb.toString(); } TreeNode Deserialize(String str) { index++; int len = str.length(); if(index >= len){ return null; } String[] strr = str.split(","); TreeNode node = null; if(!strr[index].equals("#")){ node = new TreeNode(Integer.valueOf(strr[index])); node.left = Deserialize(str); node.right = Deserialize(str); } return node; } }
