建筑工程证书查询,免费seo关键词优化方案,网站开发建设企业,六安建六安建设网站文章目录 非递归法前序遍历后序遍历中序遍历 递归法DFS 非递归法
通过栈Stack来模拟递归。
前序遍历
LeetCode 144
前序遍历#xff1a;1 2 3
定义#xff1a;存放答案的List、栈Stack
将root入栈出栈#xff1a;node#xff0c;为null则舍弃将node放入list将node.r… 文章目录 非递归法前序遍历后序遍历中序遍历 递归法DFS 非递归法
通过栈Stack来模拟递归。
前序遍历
LeetCode 144
前序遍历1 2 3
定义存放答案的List、栈Stack
将root入栈出栈node为null则舍弃将node放入list将node.right入栈将node.left入栈栈不为空则重复2-5步
为了让左节点优先于右节点出栈因此先将右节点入栈。
class Solution {public ListInteger preorderTraversal(TreeNode root) {StackTreeNode stack new Stack();ListInteger list new LinkedList();stack.push(root);while(!stack.empty()){TreeNode node stack.pop();if(nodenull)continue;list.add(node.val);stack.push(node.right);stack.push(node.left);}return list;}
}后序遍历
LeetCode 145
后序遍历2 3 1
后序遍历仅需在前序遍历的代码中修改3处即可。
由前序遍历1 2 3 改为 1 3 2 再翻转为 2 3 1即为答案。
class Solution {public ListInteger postorderTraversal(TreeNode root) {StackTreeNode stack new Stack();ListInteger list new LinkedList();stack.push(root);while(!stack.empty()){TreeNode node stack.pop();if(node null)continue;list.add(node.val);stack.push(node.left); // 先放入左节点stack.push(node.right); }Collections.reverse(list); // 反转return list;}
}中序遍历
LeetCode 94
中序遍历代码与前序和后续不同。 中序遍历 4 2 5 1 3。
思考要想先输出4则需要将左节点持续入栈直到为null此时出栈即为4然后将其右节点入栈…
同样的定义存放结果的list和栈stack。
cur rootcur不为空或者栈不为空循环 将cur入栈并将cur赋值其左节点直到为空出站node将node加入list将node赋值为node.left重复2 - 5步
class Solution {public ListInteger inorderTraversal(TreeNode root) {StackTreeNode stack new Stack();ListInteger list new LinkedList();TreeNode cur root;while(cur!null||!stack.empty()){while(cur!null){stack.push(cur);cur cur.left;}TreeNode node stack.pop(); list.add(node.val);cur node.right;}return list;}
}递归法DFS
class Solution {ListInteger list1 new LinkedList(); // 前序ListInteger list2 new LinkedList(); // 中序ListInteger list3 new LinkedList(); // 后序public ListInteger inorderTraversal(TreeNode root) {traverse(root);return list2; }void traverse(TreeNode root){if(rootnull)return;list1.add(root.val); traverse(root.left); // 递归左节点list2.add(root.val);traverse(root.right); // 递归右节点list3.add(root.val);}}参考
cyc2018代码随想录 B站
