144. 二叉树的前序遍历
问题描述
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
代码实现-迭代
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
while(root != null || !stack.isEmpty()){
while(root != null){
res.add(root.val);
stack.push(root);
root = root.left;
}
root = stack.pop();
root = root.right;
}
return res;
}
}
145. 二叉树的后序遍历
问题描述
给你二叉树的根节点 root ，返回它节点值的 后序 遍历。
代码实现-递归
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
postorder(root, res);
return res;
}
public void postorder(TreeNode root, List<Integer> res){
if(root == null){
return;
}
postorder(root.left, res);
postorder(root.right, res);
res.add(root.val);
}
}
173. 二叉搜索树迭代器
问题描述
实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。
调用 next() 将返回二叉搜索树中的下一个最小的数。
解题思路1
在迭代器的构造函数里，将二叉树的中序遍历结果读入队列。然后调用next()相当于队头节点出队；hasNext()相当于判断队列是否为空
代码实现1
/**
* 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;
* }
* }
*/
class BSTIterator {
//定义队列存储树的中序遍历结果
private Queue<Integer> q = new LinkedList<>();
private void inorder(TreeNode root){
if(root == null){
return;
}
inorder(root.left);
q.offer(root.val);
inorder(root.right);
}
public BSTIterator(TreeNode root) {
inorder(root);
}
public int next() {
return q.remove();
}
public boolean hasNext() {
return !q.isEmpty();
}
}
/**
* Your BSTIterator object will be instantiated and called as such:
* BSTIterator obj = new BSTIterator(root);
* int param_1 = obj.next();
* boolean param_2 = obj.hasNext();
*/
解题思路2
上一种解法引入了队列作为中间数据结构，其空间复杂度为O(n)，n是二叉树的所有节点数量；可以通过自己维护中间栈进行迭代的方法，来将空间复杂度降低到 O(h)，h是二叉搜索树的层高。
具体做法是：首先在迭代器构造函数中将当前节点及左子树中的左子节点都压入栈中；然后，在每次调用next后，将当前节点的右子树中的左子节点入栈。
代码实现2
class BSTIterator {
Stack<TreeNode> stack = new Stack<>();
private void addLeft(TreeNode root){
if(root == null){
return;
}
stack.push(root);
while(root.left != null){
stack.push(root.left);
root = root.left;
}
}
public BSTIterator(TreeNode root) {
addLeft(root);
}
public int next() {
TreeNode cur = stack.pop();
addLeft(cur.right);
return cur.val;
}
public boolean hasNext() {
return !stack.isEmpty();
}
}
199. 二叉树的右视图
问题描述
给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
解题思路
层序遍历二叉树，将每层最后一个节点加入结果数组
代码实现
/**
* 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;
* }
* }
*/
class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> res = new ArrayList<>();
Queue<TreeNode> q = new LinkedList<>();
if(root != null){
//根节点入队
q.offer(root);
}
while(!q.isEmpty()){
int levelSize = q.size();
for(int i = 0; i < levelSize; i++){
//队头节点出队
TreeNode temp = q.remove();
//取每层最后一个节点值加入结果数组
if(i == levelSize -1){
res.add(temp.val);
}
//队头节点左、右子节点入队
if(temp.left != null){
q.offer(temp.left);
}
if(temp.right != null){
q.offer(temp.right);
}
}
}
return res;
}
}
