网站建设优化解析,手机app设计方案,多语言免费网站建设,WordPress扫码基础概念#xff1a;前中后序遍历 1/ \2 3/ \ \
4 5 6层次遍历顺序#xff1a;[1 2 3 4 5 6]前序遍历顺序#xff1a;[1 2 4 5 3 6]中序遍历顺序#xff1a;[4 2 5 1 3 6]后序遍历顺序#xff1a;[4 5 2 6 3 1]
层次遍历使用 BFS 实现#xff0c;利用的就是 BFS…基础概念前中后序遍历 1/ \2 3/ \ \
4 5 6层次遍历顺序[1 2 3 4 5 6]前序遍历顺序[1 2 4 5 3 6]中序遍历顺序[4 2 5 1 3 6]后序遍历顺序[4 5 2 6 3 1]
层次遍历使用 BFS 实现利用的就是 BFS 一层一层遍历的特性而前序、中序、后序遍历利用了 DFS 实现。
前序、中序、后序遍只是在对节点访问的顺序有一点不同其它都相同。
① 前序
void dfs(TreeNode root) {visit(root);dfs(root.left);dfs(root.right);
}② 中序
void dfs(TreeNode root) {dfs(root.left);visit(root);dfs(root.right);
}③ 后序
void dfs(TreeNode root) {dfs(root.left);dfs(root.right);visit(root);
}145. 二叉树的后序遍历
给你一棵二叉树的根节点 root 返回其节点值的 后序遍历 。 输入root [1,null,2,3] 输出[3,2,1] 示例 2 输入root [] 输出[] 示例 3 输入root [1] 输出[1] 提示
树中节点的数目在范围 [0, 100] 内-100 Node.val 100
进阶 递归算法很简单你可以通过迭代算法完成吗
思路
法一DFS
递归见上面的基础概念。
法二迭代
后序的迭代遍历可以理解成 ” 前序遍历 “ 的反转前序遍历
这个 ”前序遍历 “ 的遍历顺序为根节点右子树、左子树
代码(Java、C)
法一递归 Java
/*** 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 ListInteger ans new ArrayList();public ListInteger postorderTraversal(TreeNode root) {dfs(root);return ans;}public void dfs(TreeNode root){if(root null) return;dfs(root.left);dfs(root.right);ans.add(root.val);}
}C
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vectorint ans;vectorint postorderTraversal(TreeNode* root) {dfs(root);return ans;}void dfs(TreeNode* root){if(root nullptr) return;dfs(root-left);dfs(root-right);ans.push_back(root-val);}
};法二迭代 Java
class Solution {public ListInteger postorderTraversal(TreeNode root) {ListInteger ans new ArrayList();if(root null) return ans;StackTreeNode stk new Stack();stk.push(root);while(!stk.isEmpty()){root stk.pop();ans.add(root.val);if(root.left ! null) stk.push(root.left);if(root.right ! null) stk.push(root.right);}Collections.reverse(ans);return ans;}
}C
class Solution {
public:vectorint postorderTraversal(TreeNode* root) {vectorint ans;if(root nullptr) return ans;stackTreeNode* stk;stk.push(root);while(!stk.empty()){root stk.top();stk.pop();ans.push_back(root-val);if(root-left ! nullptr) stk.push(root-left);if(root-right ! nullptr) stk.push(root-right);}reverse(ans.begin(), ans.end());return ans;}
};运行结果 复杂度分析
时间复杂度 O ( n ) O(n) O(n)其中 n 是二叉树的节点数。每一个节点恰好被遍历一次。空间复杂度 O ( n ) O(n) O(n)为递归或迭代过程中栈的开销平均情况下为 O ( l o g n ) O(logn) O(logn)最坏情况下树呈现链状为 O ( n ) O(n) O(n)。
题目来源力扣。 放弃一件事很容易每天能坚持一件事一定很酷一起每日一题吧 关注我 leetCode专栏每日更新 注 如有不足欢迎指正
