题目：单值二叉树
如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。只有给定的树是单值二叉树时，才返回 true；否则返回 false。复制代码
示例：
输入：[1,1,1,1,1,null,1]输出：true复制代码
输入：[2,2,2,5,2]输出：false复制代码
思考：
这道题只要遍历二叉树的每个节点然后比较每个节点的值即可。所以这题其实就是回顾二叉树的遍历方法。复制代码
实现：
/** * Definition for a binary tree node. * public class TreeNode {* int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public ArrayList list = new ArrayList<>(); public boolean isUnivalTree(TreeNode root) { //遍历二叉树将节点值加入到list中 dfs(root); //比较节点值是否相等 for (int count = 1; count < list.size(); count++) { if (list.get(0) != list.get(count)) { return false; } } return true; } //递归遍历二叉树 private void dfs(TreeNode node) { if (node != null) { list.add(node.val); dfs(node.left); dfs(node.right); } }}复制代码 二叉树遍历方法：
深度遍历：
1.先序遍历
遍历顺序：根节点-左子节点-右子节点 递归实现：private void dfs(TreeNode node) { if (node != null) { //将根节点放入list list.add(node.val); //递归左节点 dfs(node.left); //递归右节点 dfs(node.right); } }复制代码 非递归实现：
public void dfs(TreeNode root) { //非递归需要用栈来记录节点情况 Stack stack = new Stack (); //记录当前节点 TreeNode cur = root; //当前节点不为空且栈不为空时循环 while (cur != null || !stack.isEmpty()) { //当前节点不为空，一直循环，该循环会一直遍历根节点的左子节点，左子节点的左子节点...直至最左叶子节点。 while (cur != null) { //将该节点值放入list list.add(cur.val); //将当前节点入栈 stack.push(cur); //当前节点指向其左节点 cur = cur.left; } //遍历到最左叶子节点跳出循环 //栈不为空时，取出栈顶节点，即最左叶子节点，将当前节点指向其右子节点。 //之后回到外层循环，再遍历右子节点的左子节点 if (!stack.isEmpty()) { //取出栈顶元素 TreeNode node = stack.pop(); //当前节点指向栈顶节点的右子节点 cur = node.right; } }复制代码 2.中序遍历
遍历顺序：左子节点-根节点-右子节点 递归实现：private void dfs(TreeNode node) { if (node != null) { //递归左节点 dfs(node.left); //将根节点放入list list.add(node.val); //递归右节点 dfs(node.right); } }复制代码 非递归实现：
public void dfs(TreeNode root) { //非递归需要用栈来记录节点情况 Stack stack = new Stack (); //记录当前节点 TreeNode cur = root; //当前节点不为空且栈不为空时循环 while (cur != null || !stack.isEmpty()) { //当前节点不为空，一直循环，该循环会一直遍历根节点的左子节点，左子节点的左子节点...直至最左叶子节点。 while (cur != null) { //将当前节点入栈 stack.push(cur); //当前节点指向其左节点 cur = cur.left; } //遍历到最左叶子节点跳出循环 //栈不为空时，取出栈顶节点，即最左叶子节点，将该节点放入list，再将当前节点指向该节点的右子节点 //之后回到外层循环，再遍历右子节点的左子节点 if (!stack.isEmpty()) { //取出栈顶节点 TreeNode node = stack.pop(); //将该节点放入list list.add(node.val); //将当前节点指向该节点的右子节点 cur = node.right; } } }复制代码 3.后序遍历
遍历顺序：左子节点-根节点-右子节点 递归实现：private void dfs(TreeNode node) { if (node != null) { //递归左节点 dfs(node.left); //递归右节点 dfs(node.right); //将根节点放入list list.add(node.val); } }复制代码 非递归实现：
public void dfs(TreeNode root) { //非递归需要用栈来记录节点情况 Stack stack = new Stack (); //记录当前节点 TreeNode cur = root; //后续遍历需要一个记录当前节点右子节点是否已被访问的标记，当cur.right=flag时说明该节点右子节点已被访问过 TreeNode flag = null; //当前节点不为空时一直循环，该循环会一直遍历根节点的左子节点，左子节点的左子节点...直至最左叶子节点。 while (cur != null) { //将当前节点入栈 stack.push(cur); //当前节点指向其左节点 cur = cur.left; } //遍历到最左叶子节点跳出循环 //栈不为空时循环取出栈顶节点，即最左叶子节点 while (!stack.isEmpty()) { //取出栈顶节点，将当前节点指向栈顶节点 cur = stack.pop(); //如果当前节点的右子节点为空或者右子节点被访问过 if (cur.right == null || cur.right == flag) { //将当前节点放入list list.add(cur.val); //记录当前节点 flag = cur; } else { //当前节点不为空且没被访问过，则将当前节点入栈 stack.push(cur); //将当前接单指向其右子节点 cur = cur.right; //右子节点不为空 while (cur != null) { //将右子节点入栈 stack.push(cur); //再将当前节点指向其左子节点 cur = cur.left; } } } }复制代码 层次遍历：
遍历顺序：按从顶层到底层的次序访问树中元素，在同一层中，从左到右进行访问。
实现：public void bfs(TreeNode root) { //层次遍历需要用队列来记录节点情况 ArrayDeque queue = new ArrayDeque (); //记录当前节点 TreeNode cur = root; //将根节点加入队列 queue.add(root); //队列不为空循环队列 while (!queue.isEmpty() ) { //取出队列中首个节点 TreeNode node = queue.remove(); //将该节点放入list list.add(node.val); //左子节点不为空将左子节点入队 if (node.left != null) { queue.add(node.left); } //右子节点不为空将右子节点入队 if (node.right != null) { queue.add(node.right); } } }复制代码