淮安哪里有做网站的人,合肥画册设计公司,网站建设需求调查表,wordpress超链接下划线1.二叉树的递归遍历
回顾了递归的套路#xff1a;1.返回值传入参数 2.结束条件 3.写具体的每一个递归单位
而在二叉树的三种遍历都没有返回值#xff0c;传入当前node节点和所给框架下的返回值数组res
当传入的节点是null时结束递归
每个递归单位包含输出当前节点递归左孩…1.二叉树的递归遍历
回顾了递归的套路1.返回值传入参数 2.结束条件 3.写具体的每一个递归单位
而在二叉树的三种遍历都没有返回值传入当前node节点和所给框架下的返回值数组res
当传入的节点是null时结束递归
每个递归单位包含输出当前节点递归左孩子递归右孩子改变输出的位置即可实现三种遍历
144.二叉树的前序遍历
class Solution {public ListInteger preorderTraversal(TreeNode root) {ListInteger res new ArrayList();pre(root,res);return res;}void pre(TreeNode node, ListInteger res){if(node null) return;res.add(node.val);pre(node.left,res);pre(node.right,res);}
}
145.二叉树的后序遍历
class Solution {public ListInteger postorderTraversal(TreeNode root) {ListInteger res new ArrayList();post(root,res);return res;}void post(TreeNode node, ListInteger res){if(node null) return;post(node.left,res);post(node.right,res);res.add(node.val);}
}
94.二叉树的中序遍历
class Solution {public ListInteger inorderTraversal(TreeNode root) {ListInteger res new ArrayList();in(root,res);return res;}void in(TreeNode node, ListInteger res){if(node null) return;in(node.left,res);res.add(node.val);in(node.right,res);}
}
2.二叉树的迭代遍历
144.二叉树的前序遍历
众所周知递归都可以改成循环本质上还是自己模拟递归栈的过程
前序遍历模拟最简单因为处理的节点和先访问的节点一致可以直接将节点的左右孩子入栈
class Solution {public ListInteger preorderTraversal(TreeNode root) {ListInteger res new ArrayList();if (root null) return res;DequeTreeNode s new LinkedList();s.push(root);while (!s.isEmpty()) {TreeNode cur s.pop();res.add(cur.val);if (cur.right ! null) s.push(cur.right);if (cur.left ! null) s.push(cur.left);}return res;}
}
145.二叉树的后序遍历(opens new window)
稍微改动下前序遍历的代码左右孩子改下顺序再将最后的结果逆序就可以得到后序遍历的结果
Java里的集合进行逆序Collections.reverse(res)
class Solution {public ListInteger postorderTraversal(TreeNode root) {ListInteger res new ArrayList();if (root null) return res;DequeTreeNode s new LinkedList();s.push(root);while (!s.isEmpty()) {TreeNode cur s.pop();res.add(cur.val);if (cur.left ! null) s.push(cur.left);if (cur.right ! null) s.push(cur.right);}Collections.reverse(res);return res;}
}
94.二叉树的中序遍历
中序遍历没办法像前序遍历直接模拟需要一路向左入栈左孩子为空后处理再查看右孩子
代码上while内的条件直接作为两个分支处理
class Solution {public ListInteger inorderTraversal(TreeNode root) {ListInteger res new LinkedList();if (root null) return res;DequeTreeNode s new LinkedList();TreeNode cur root;while(cur ! null || !s.isEmpty()){if (cur ! null) {s.push(cur);cur cur.left;}else {cur s.pop();res.add(cur.val);cur cur.right;}}return res;}
}
3.二叉树的层序遍历
按照广度优先搜索从根节点第一层开始输出节点后将节点的左右孩子入队
注意代码中队列使用offer和poll以及容器的size要在循环前保存
class Solution {public ListListInteger levelOrder(TreeNode root) {ListListInteger res new ArrayList();if (root null) return res;DequeTreeNode q new LinkedList();q.offer(root);while(!q.isEmpty()){ListInteger listnew ArrayList();int n q.size();for (int i 0; i n; i) {TreeNode node q.poll();list.add(node.val);if (node.left ! null) q.offer(node.left);if (node.right ! null) q.offer(node.right);}res.add(list);}return res;}
}
