102. 二叉树的层序遍历

思路：

以前的笔记

代码：

class Solution {public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> list = new ArrayList<List<Integer>>();if (root == null) {return list;}Queue<TreeNode> queue = new LinkedList<TreeNode>();queue.offer(root);while (!queue.isEmpty())  {List<Integer> levelList = new LinkedList<>();int len = queue.size();// 遍历这一层for (int i = 0; i < len; i++) {TreeNode node = queue.poll();levelList.add(node.val);if (node.left != null) {queue.offer(node.left);}if (node.right != null) {queue.offer(node.right);}}list.add(levelList);}return list;}
}

226. 翻转二叉树

思路：

本题目可以使用递归，迭代和层序遍历来做。需要注意的是迭代的方法中，只能使用前序和后序遍历，因为使用中序遍历会对同一个子树翻转两次。

代码：

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*///  DFS递归方法
class Solution {public TreeNode invertTree(TreeNode root) {if (root == null) {return root;}swapChildren(root);invertTree(root.left);invertTree(root.right);return root;}public void swapChildren(TreeNode node) {TreeNode tem = node.left;node.left = node.right;node.right = tem;}
}// 迭代的前序遍历
class Solution {public TreeNode invertTree(TreeNode root) {if (root == null) {return root;}Stack<TreeNode> stack = new Stack<>();stack.push(root);while (!stack.isEmpty()) {TreeNode node = stack.pop();swapChildren(node);if (node.right != null) {stack.push(node.right);}if (node.left != null) {stack.push(node.left);}}return root;}public void swapChildren(TreeNode node) {TreeNode tem = node.left;node.left = node.right;node.right = tem;}
}// 层序遍历
class Solution {public TreeNode invertTree(TreeNode root) {if (root == null) {return root;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {TreeNode node = queue.poll();swapChildren(node);if (node.left != null) {queue.offer(node.left);}if (node.right != null) {queue.offer(node.right);}}return root;}public void swapChildren(TreeNode node) {TreeNode tem = node.left;node.left = node.right;node.right = tem;}
}

101. 对称二叉树

思路：

dfs：判断一个树是否对称，从根节点开始，看左子树和右子树是否对称。】

bfs：通过队列进行遍历比较，把左子树根节点和右子树根节点入队列，比较因素同dfs。需要注意的是，后续入队列时，左子树的左节点和右子树的右节点，左子树的右节点和右子树的左节点一起入队，两两入队列，两两出队列比较。

代码：

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/// dfs
class Solution {public boolean isSymmetric(TreeNode root) {if (root == null) {return true;}return compare(root.left, root.right);}// 判断一个节点的左子树和右子树是否对称public boolean compare(TreeNode left, TreeNode right) {// 左子树和右子树都为空，对称if (left == null && right == null) {return true;}// 左右子树只有一个为空，不对称if (left == null || right == null) {return false;}// 左子树根节点值不等于右子树根节点值，不对称if (left.val != right.val) {return false;}// 只剩下left.val和right.val相等的情况// 需要判断left.left和right.right, left.right和right.left是否对称// boolean outside = compare(left.left, right.right);// boolean inside = compare(left.right, right.left);// return outside && inside;// 简化return compare(left.left, right.right) && compare(left.right, right.left);}
}// bfs
class Solution {public boolean isSymmetric(TreeNode root) {if (root == null) {return true;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root.right);queue.offer(root.left);while (!queue.isEmpty()) {TreeNode right = queue.poll();TreeNode left = queue.poll();if (left == null && right == null) {continue;}if (left == null || right == null) {return false;}if (left.val != right.val) {return false;}// left.val等于right.valqueue.offer(left.left);queue.offer(right.right);queue.offer(left.right);queue.offer(right.left);}return true;}
}

这两道题目基本和本题是一样的，只要稍加修改就可以AC。

100.相同的树(opens new window)
572.另一个树的子树

100. 相同的树

代码：

// dfs
class Solution {public boolean isSameTree(TreeNode p, TreeNode q) {if (p == null && q == null) {return true;}if (p == null || q == null) {return false;}if (p.val != q.val) {return false;} // p.val和q.val相等的情况return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);}
}// bfs
class Solution {public boolean isSameTree(TreeNode p, TreeNode q) {if (p == null && q == null) {return true;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(p);queue.offer(q);while (!queue.isEmpty()) {TreeNode left = queue.poll();TreeNode right = queue.poll();if (left == null && right == null) {continue;}if (left == null || right == null) {return false;}if (left.val != right.val) {return false;}queue.offer(left.left);queue.offer(right.left);queue.offer(left.right);queue.offer(right.right);}return true;}
}