題目：單值二叉樹

---

如果二叉樹每個節(jié)點(diǎn)都具有相同的值，那么該二叉樹就是單值二叉樹。 只有給定的樹是單值二叉樹時，才返回 true；否則返回 false。 復(fù)制代碼

示例：

---

輸入：[1,1,1,1,1,null,1] 輸出：true 復(fù)制代碼

輸入：[2,2,2,5,2] 輸出：false 復(fù)制代碼

思考：

---

這道題只要遍歷二叉樹的每個節(jié)點(diǎn)然后比較每個節(jié)點(diǎn)的值即可。所以這題其實(shí)就是回顧二叉樹的遍歷方法。 復(fù)制代碼

實(shí)現(xiàn)：

---

/*** Definition for a binary tree node.* public class TreeNode { * int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val = x; }* }*/class Solution {public ArrayList<Integer> list = new ArrayList<>();public boolean isUnivalTree(TreeNode root) {//遍歷二叉樹將節(jié)點(diǎn)值加入到list中dfs(root);//比較節(jié)點(diǎn)值是否相等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);}} } 復(fù)制代碼

二叉樹遍歷方法：

---

深度遍歷：

1.先序遍歷
遍歷順序：根節(jié)點(diǎn)-左子節(jié)點(diǎn)-右子節(jié)點(diǎn)
遞歸實(shí)現(xiàn)：

private void dfs(TreeNode node) {if (node != null) {//將根節(jié)點(diǎn)放入listlist.add(node.val);//遞歸左節(jié)點(diǎn)dfs(node.left);//遞歸右節(jié)點(diǎn)dfs(node.right);}} 復(fù)制代碼

非遞歸實(shí)現(xiàn)：

public void dfs(TreeNode root) {//非遞歸需要用棧來記錄節(jié)點(diǎn)情況Stack<TreeNode> stack = new Stack<TreeNode>();//記錄當(dāng)前節(jié)點(diǎn)TreeNode cur = root;//當(dāng)前節(jié)點(diǎn)不為空且棧不為空時循環(huán)while (cur != null || !stack.isEmpty()) {//當(dāng)前節(jié)點(diǎn)不為空，一直循環(huán)，該循環(huán)會一直遍歷根節(jié)點(diǎn)的左子節(jié)點(diǎn)，左子節(jié)點(diǎn)的左子節(jié)點(diǎn)...直至最左葉子節(jié)點(diǎn)。while (cur != null) {//將該節(jié)點(diǎn)值放入listlist.add(cur.val);//將當(dāng)前節(jié)點(diǎn)入棧stack.push(cur);//當(dāng)前節(jié)點(diǎn)指向其左節(jié)點(diǎn)cur = cur.left;} //遍歷到最左葉子節(jié)點(diǎn)跳出循環(huán)//棧不為空時，取出棧頂節(jié)點(diǎn)，即最左葉子節(jié)點(diǎn)，將當(dāng)前節(jié)點(diǎn)指向其右子節(jié)點(diǎn)。//之后回到外層循環(huán)，再遍歷右子節(jié)點(diǎn)的左子節(jié)點(diǎn)if (!stack.isEmpty()) {//取出棧頂元素TreeNode node = stack.pop();//當(dāng)前節(jié)點(diǎn)指向棧頂節(jié)點(diǎn)的右子節(jié)點(diǎn)cur = node.right;}} 復(fù)制代碼

2.中序遍歷
遍歷順序：左子節(jié)點(diǎn)-根節(jié)點(diǎn)-右子節(jié)點(diǎn)
遞歸實(shí)現(xiàn)：

private void dfs(TreeNode node) {if (node != null) {//遞歸左節(jié)點(diǎn)dfs(node.left);//將根節(jié)點(diǎn)放入listlist.add(node.val);//遞歸右節(jié)點(diǎn)dfs(node.right);}} 復(fù)制代碼

非遞歸實(shí)現(xiàn)：

public void dfs(TreeNode root) {//非遞歸需要用棧來記錄節(jié)點(diǎn)情況Stack<TreeNode> stack = new Stack<TreeNode>();//記錄當(dāng)前節(jié)點(diǎn)TreeNode cur = root;//當(dāng)前節(jié)點(diǎn)不為空且棧不為空時循環(huán)while (cur != null || !stack.isEmpty()) {//當(dāng)前節(jié)點(diǎn)不為空，一直循環(huán)，該循環(huán)會一直遍歷根節(jié)點(diǎn)的左子節(jié)點(diǎn)，左子節(jié)點(diǎn)的左子節(jié)點(diǎn)...直至最左葉子節(jié)點(diǎn)。while (cur != null) {//將當(dāng)前節(jié)點(diǎn)入棧stack.push(cur);//當(dāng)前節(jié)點(diǎn)指向其左節(jié)點(diǎn)cur = cur.left;}//遍歷到最左葉子節(jié)點(diǎn)跳出循環(huán)//棧不為空時，取出棧頂節(jié)點(diǎn)，即最左葉子節(jié)點(diǎn)，將該節(jié)點(diǎn)放入list，再將當(dāng)前節(jié)點(diǎn)指向該節(jié)點(diǎn)的右子節(jié)點(diǎn)//之后回到外層循環(huán)，再遍歷右子節(jié)點(diǎn)的左子節(jié)點(diǎn)if (!stack.isEmpty()) {//取出棧頂節(jié)點(diǎn)TreeNode node = stack.pop();//將該節(jié)點(diǎn)放入listlist.add(node.val);//將當(dāng)前節(jié)點(diǎn)指向該節(jié)點(diǎn)的右子節(jié)點(diǎn)cur = node.right;}}} 復(fù)制代碼

3.后序遍歷
遍歷順序：左子節(jié)點(diǎn)-根節(jié)點(diǎn)-右子節(jié)點(diǎn)
遞歸實(shí)現(xiàn)：

private void dfs(TreeNode node) {if (node != null) {//遞歸左節(jié)點(diǎn)dfs(node.left);//遞歸右節(jié)點(diǎn)dfs(node.right);//將根節(jié)點(diǎn)放入listlist.add(node.val);}} 復(fù)制代碼

非遞歸實(shí)現(xiàn)：

public void dfs(TreeNode root) {//非遞歸需要用棧來記錄節(jié)點(diǎn)情況Stack<TreeNode> stack = new Stack<TreeNode>();//記錄當(dāng)前節(jié)點(diǎn)TreeNode cur = root;//后續(xù)遍歷需要一個記錄當(dāng)前節(jié)點(diǎn)右子節(jié)點(diǎn)是否已被訪問的標(biāo)記，當(dāng)cur.right=flag時說明該節(jié)點(diǎn)右子節(jié)點(diǎn)已被訪問過TreeNode flag = null;//當(dāng)前節(jié)點(diǎn)不為空時一直循環(huán)，該循環(huán)會一直遍歷根節(jié)點(diǎn)的左子節(jié)點(diǎn)，左子節(jié)點(diǎn)的左子節(jié)點(diǎn)...直至最左葉子節(jié)點(diǎn)。while (cur != null) {//將當(dāng)前節(jié)點(diǎn)入棧stack.push(cur);//當(dāng)前節(jié)點(diǎn)指向其左節(jié)點(diǎn)cur = cur.left;}//遍歷到最左葉子節(jié)點(diǎn)跳出循環(huán)//棧不為空時循環(huán)取出棧頂節(jié)點(diǎn)，即最左葉子節(jié)點(diǎn)while (!stack.isEmpty()) {//取出棧頂節(jié)點(diǎn)，將當(dāng)前節(jié)點(diǎn)指向棧頂節(jié)點(diǎn)cur = stack.pop();//如果當(dāng)前節(jié)點(diǎn)的右子節(jié)點(diǎn)為空或者右子節(jié)點(diǎn)被訪問過if (cur.right == null || cur.right == flag) {//將當(dāng)前節(jié)點(diǎn)放入listlist.add(cur.val);//記錄當(dāng)前節(jié)點(diǎn)flag = cur;} else {//當(dāng)前節(jié)點(diǎn)不為空且沒被訪問過，則將當(dāng)前節(jié)點(diǎn)入棧stack.push(cur);//將當(dāng)前接單指向其右子節(jié)點(diǎn)cur = cur.right;//右子節(jié)點(diǎn)不為空while (cur != null) {//將右子節(jié)點(diǎn)入棧stack.push(cur);//再將當(dāng)前節(jié)點(diǎn)指向其左子節(jié)點(diǎn)cur = cur.left;}}}} 復(fù)制代碼

層次遍歷：

遍歷順序：按從頂層到底層的次序訪問樹中元素，在同一層中，從左到右進(jìn)行訪問。
實(shí)現(xiàn)：

public void bfs(TreeNode root) {//層次遍歷需要用隊(duì)列來記錄節(jié)點(diǎn)情況ArrayDeque<TreeNode> queue = new ArrayDeque<TreeNode>();//記錄當(dāng)前節(jié)點(diǎn)TreeNode cur = root;//將根節(jié)點(diǎn)加入隊(duì)列queue.add(root);//隊(duì)列不為空循環(huán)隊(duì)列while (!queue.isEmpty() ) {//取出隊(duì)列中首個節(jié)點(diǎn)TreeNode node = queue.remove();//將該節(jié)點(diǎn)放入listlist.add(node.val);//左子節(jié)點(diǎn)不為空將左子節(jié)點(diǎn)入隊(duì) if (node.left != null) {queue.add(node.left);}//右子節(jié)點(diǎn)不為空將右子節(jié)點(diǎn)入隊(duì)if (node.right != null) {queue.add(node.right);}}}復(fù)制代碼

轉(zhuǎn)載于:https://juejin.im/post/5cb416aa6fb9a068547349c3

總結(jié)

以上是生活随笔為你收集整理的LeetCode每日一题: 单值二叉树（No.965）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。