翻转二叉树
解法一
递归
class Solution { public TreeNode invertTree(TreeNode root) { if(root == null) return null; // 获取左节点 TreeNode left = invertTree(root.left); //获取右节点 TreeNode right = invertTree(root.right); root.left = right; root.right = left; return root; } }
解法二
迭代
class Solution { public TreeNode invertTree(TreeNode root) { if(root == null) return null; LinkedList<TreeNode> list = new LinkedList<>(); list.add(root); while(!list.isEmpty()){ TreeNode node = list.poll(); TreeNode left = node.left; TreeNode right = node.right; node.left = right; node.right = left; if(node.left != null){ list.add(node.left); } if(node.right != null){ list.add(node.right); } } return root; } }
二叉树的最近公共祖先
解法一
递归
存在三种情况
p,q在root的两边，那么返回root
p,q在root的一边。返回p或者q
p,q不在，返回null
class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if(root == null || root == p || root == q) return root; TreeNode left = lowestCommonAncestor(root.left,p,q); TreeNode right = lowestCommonAncestor(root.right,p,q); if(left == null) return right; if(right == null) return left; return root; } }
二叉树的序列化与反序列化
解法一
前序遍历
public class Codec { // Encodes a tree to a single string. public String serialize(TreeNode root) { if(root == null) return ""; StringBuilder sb = new StringBuilder(); rserialize(root,sb); return sb.toString(); } // Decodes your encoded data to tree. public TreeNode deserialize(String data) { String[] split = data.split(","); List<String> list = new ArrayList<>(Arrays.asList(split)); return rdeserialize(list); } public void rserialize(TreeNode root,StringBuilder sb){ if(root == null){ sb.append("null,"); return; } sb.append(root.val+","); rserialize(root.left,sb); rserialize(root.right,sb); } public TreeNode rdeserialize(List<String> list){ if(list == null || list.size() == 0 || list.get(0).equals("null") || list.get(0).equals("")){ list.remove(0); return null; } TreeNode node = new TreeNode(Integer.valueOf(list.get(0))); list.remove(0); node.left = rdeserialize(list); node.right = rdeserialize(list); return node; } }
