Java 的 ArrayDeque 的 API 介绍，递归和迭代实现二叉树前序、中序、后序遍历，求解《965. 单值二叉树》
Java · ArrayDeque
栈 和 双端队列 的数组实现
基本
size()长度isEmpty()是否为空contain(Object o)是否存在元素clear()清空队列clone()复制 · 克隆
栈
push(E e)栈顶添加元素pop()移除栈顶元素，没有，返回异常
双端队列
添加元素
addFirst(E e)队头添加元素add(E e)/addLast(E e)队尾后添加元素offerFirst(E e)队头添加元素，返回是否添加成功offer(E e)/offerLast(E e)队尾添加元素，返回是否添加成功
删除元素
remove()/removeFirst()删除并返回第一个元素，如果元素为null，抛出异常removeLast()删除并返回最后一个元素，如果元素为null，抛出异常removeFirstOccurrence(Object o)删除第一次出现的指定元素removeLastOccurrence(Object o)删除最后一次出现的指定元素poll()/pollFirst()删除并返回第一个元素，如果元素为null，返回nullpollLast()删除并返回最后一个元素，如果元素为null，返回null
获取元素
peek()获取第一个元素，没有，返回nullelement()获取第一个元素，没有，抛出异常getFirst()获取第一个元素，没有，抛出异常getLast()获取最后一个元素，没有，抛出异常
迭代器
iterator()迭代器，前 → 后descendingIterator()迭代器，后 → 前toArray()转成数组
例题
965. 单值二叉树
如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。
只有给定的树是单值二叉树时，才返回 true；否则返回 false。
示例1：
输入：[1,1,1,1,1,null,1]
输出：true
提示：
给定树的节点数范围是 [1, 100]。
每个节点的值都是整数，范围为 [0, 99]
答案
递归 · 前序遍历
var isUnivalTree = function(root) { // 递归 · 前序遍历
const v = root.val
const d = n => {
if (n === null) return true
if (n.val !== v) return false
return d(n.left) && d(n.right)
}
return d(root)
};递归 · 中序遍历
function isUnivalTree(root: TreeNode | null): boolean { // 递归 · 中序遍历
const v = root.val
const d = n => {
if (n === null) return true
if (d(n.left) === false) return false
if (n.val !== v) return false
if (d(n.right) === false) return false
return true
}
return d(root)
};递归 · 后序遍历
class Solution {
private $v;
function isUnivalTree($root) { // 递归 · 后序遍历
$this->v = $root->val;
return $this->d($root);
}
function d($n) {
if ($n === null) return true;
if ($this->d($n->left) === false) return false;
if ($this->d($n->right) === false) return false;
if ($this->v !== $n->val) return false;
return true;
}
}迭代 · 单栈 · 前序遍历
func isUnivalTree(root *TreeNode) bool { // 迭代 · 前序遍历
stack := []*TreeNode{root}
for len(stack) > 0 {
n := stack[len(stack) - 1]
if n.Val != root.Val {
return false
}
stack = stack[:len(stack) - 1]
if n.Right != nil {
stack = append(stack, n.Right)
}
if n.Left != nil {
stack = append(stack, n.Left)
}
}
return true
}迭代 · 单栈 · 中序遍历
class Solution {
public boolean isUnivalTree(TreeNode root) { // 迭代 · 单栈 · 中序遍历
Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
TreeNode p = root;
while (p != null || stack.size() > 0) {
while (p != null) {
stack.push(p);
p = p.left;
}
TreeNode n = stack.pop();
if (n.val != root.val) return false;
p = n.right;
}
return true;
}
}迭代 · 莫里斯 · 中序遍历
class Solution:
def isUnivalTree(self, root: TreeNode) -> bool: # 迭代 · 莫里斯 Morris · 中序遍历
v = root.val
while root:
if root.left:
p = root.left
while p.right and p.right != root: p = p.right
if p.right == None:
p.right = root
root = root.left
else:
if root.val != v: return False
p.right = None
root = root.right
else:
if root.val != v: return False
root = root.right
return True迭代 · 单栈 · 后序遍历
class Solution(object):
def isUnivalTree(self, root): # 迭代 · 单栈 · 后序遍历
stack, p, prev = [], root, None
while p or len(stack):
while p:
stack.append(p)
p = p.left
n = stack.pop()
if n.right == None or n.right == prev:
if n.val != root.val: return False
prev = n
else:
stack.append(n)
p = n.right
return True迭代 · 双栈 · 后序遍历
class Solution {
public boolean isUnivalTree(TreeNode root) { // 迭代 · 双栈 · 后序遍历
Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
Deque<TreeNode> outStack = new ArrayDeque<TreeNode>();
stack.push(root);
while (stack.isEmpty() == false) {
TreeNode n = stack.pop();
outStack.push(n);
if (n.left != null) stack.push(n.left);
if (n.right != null) stack.push(n.right);
}
while (outStack.isEmpty() == false) {
TreeNode n = outStack.pop();
if (n.val != root.val) return false;
}
return true;
}
}