理论基础
二叉树的种类:满二叉树、完全二叉树、二叉搜索树、平衡二叉搜索树。
二叉树的遍历方式:深度遍历(前序、中序、后序),广度遍历(层次遍历)。
二叉树递归遍历
递归前序遍历代码
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new LinkedList<>();
if (root == null) {
return res;
}
// 前序遍历结果特点:第一个是根节点的值,接着是左子树,最后是右子树
res.add(root.val);
res.addAll(preorderTraversal(root.left));
res.addAll(preorderTraversal(root.right));
return res;
}
}
递归后序遍历代码
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new LinkedList<>();
if (root == null) {
return res;
}
res.addAll(postorderTraversal(root.left));
res.addAll(postorderTraversal(root.right));
res.add(root.val);
return res;
}
}
递归中序遍历代码
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new LinkedList<>();
if (root == null) {
return res;
}
res.addAll(inorderTraversal(root.left));
res.add(root.val);
res.addAll(inorderTraversal(root.right));
return res;
}
}
二叉树的迭代遍历
前序迭代遍历
思路:先将根节点放入栈中,然后从栈中弹出节点放进数组,将弹出节点的右孩子放入栈中,将弹出节点的左孩子放入栈中。直到栈空。(注意:要先将右孩子入栈,再将左孩子入栈,这样出栈的顺序才是中、左、右,才符合前序遍历)。
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
// 迭代法,利用栈辅助操作
Deque<TreeNode> stack = new ArrayDeque<>();
List<Integer> ans = new ArrayList<>();
if (root == null) return ans;
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
ans.add(node.val); // 中
if (node.right != null) {
stack.push(node.right); // 右
}
if (node.left != null) {
stack.push(node.left); // 左
}
}
// 从栈中取出来就是左 右 ,顺序是中 左 右 符合前序
return ans;
}
}
后序迭代遍历
思路:根据前序遍历来修改得到,调换左右孩子入栈的顺序,出栈顺序就是中、右、左,然后将数组反转,就得到左、右、中的遍历顺序,符合后序遍历。
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
// 迭代法,利用栈辅助操作。
Deque<TreeNode> stack = new ArrayDeque<>();
List<Integer> ans = new ArrayList<>();
if (root == null) return ans;
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
ans.add(node.val); // 中
if (node.left != null) {
stack.push(node.left); // 左
}
if (node.right != null) {
stack.push(node.right); // 右
}
}
// 从栈中取出来顺序是 右 左 ,最后顺序为 中 右 左
// 反转数组后是 左 右 中,符合后序
Collections.reverse(ans);
return ans;
}
}
中序迭代遍历
思路:迭代法中,中序遍历的处理顺序和访问顺序是不一致的,需要借助指针来帮助遍历访问节点,栈用来处理节点。先将指针指向根节点,只要指针或栈不为空,就进行遍历操作,如果指针不为空,当前元素入栈,指针指向左孩子,如果指针为空,指针指向栈中的出栈元素,将元素值存入数组中,然后指针指向当前元素的右孩子。
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
// 迭代法,用栈记录遍历过的元素
Deque<TreeNode> stack = new ArrayDeque<>();
List<Integer> ans = new ArrayList<>();
TreeNode current = root;
while (current != null || !stack.isEmpty()) {
if (current != null) {
stack.push(current);
current = current.left;
} else {
current = stack.pop();
ans.add(current.val);
current = current.right;
}
}
return ans;
}
}
二叉树的统一遍历
思路:递归遍历无法统一写法的原因是无法同时解决访问节点(遍历节点)和处理节点(将元素放进结果集)不一致的情况。解决方法是将访问的节点放入栈中,把要处理的节点也放入栈中,但紧接着要放入一个空指针作为标记。(注意:Java中Stack可以push(null)而Deque不可以)
前序代码:
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new LinkedList<>();
Stack<TreeNode> st = new Stack<>();
if (root != null) st.push(root);
while (!st.empty()) {
TreeNode node = st.peek();
if (node != null) {
// 将该节点弹出,避免重复操作,下面再将右中左节点添加到栈中
st.pop();
// 添加右节点(空节点不入栈)
if (node.right != null) st.push(node.right);
// 添加左节点(空节点不入栈)
if (node.left != null) st.push(node.left);
// 添加中节点
st.push(node);
// 中节点访问过,但是还没有处理,加入空节点做为标记。
st.push(null);
} else { // 只有遇到空节点的时候,才将下一个节点放进结果集
st.pop(); // 将空节点弹出
node = st.peek(); // 重新取出栈中元素
st.pop();
result.add(node.val); // 加入到结果集
}
}
return result;
}
}
中序代码:
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new LinkedList<>();
Stack<TreeNode> st = new Stack<>();
if (root != null) st.push(root);
while (!st.empty()) {
TreeNode node = st.peek();
if (node != null) {
// 将该节点弹出,避免重复操作,下面再将右中左节点添加到栈中
st.pop();
// 添加右节点(空节点不入栈)
if (node.right != null) st.push(node.right);
// 添加中节点
st.push(node);
// 中节点访问过,但是还没有处理,加入空节点做为标记。
st.push(null);
// 添加左节点(空节点不入栈)
if (node.left != null) st.push(node.left);
} else { // 只有遇到空节点的时候,才将下一个节点放进结果集
st.pop(); // 将空节点弹出
node = st.peek(); // 重新取出栈中元素
st.pop();
result.add(node.val); // 加入到结果集
}
}
return result;
}
}
后序代码:
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new LinkedList<>();
Stack<TreeNode> st = new Stack<>();
if (root != null) st.push(root);
while (!st.empty()) {
TreeNode node = st.peek();
if (node != null) {
// 将该节点弹出,避免重复操作,下面再将右中左节点添加到栈中
st.pop();
// 添加中节点
st.push(node);
// 中节点访问过,但是还没有处理,加入空节点做为标记。
st.push(null);
// 添加右节点(空节点不入栈)
if (node.right != null) st.push(node.right);
// 添加左节点(空节点不入栈)
if (node.left != null) st.push(node.left);
} else { // 只有遇到空节点的时候,才将下一个节点放进结果集
st.pop(); // 将空节点弹出
node = st.peek(); // 重新取出栈中元素
st.pop();
result.add(node.val); // 加入到结果集
}
}
return result;
}
}
原文地址:https://blog.csdn.net/qq_41541801/article/details/134747025
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.7code.cn/show_33152.html
如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱:suwngjj01@126.com进行投诉反馈,一经查实,立即删除!