{"id":740,"date":"2020-06-29T17:22:17","date_gmt":"2020-06-29T09:22:17","guid":{"rendered":"http:\/\/www.guanhaobo.cn\/?p=740"},"modified":"2020-06-29T17:22:17","modified_gmt":"2020-06-29T09:22:17","slug":"%e4%ba%8c%e5%8f%89%e6%a0%91%e7%9a%84%e9%81%8d%e5%8e%86","status":"publish","type":"post","link":"https:\/\/www.guanhaobo.cn\/?p=740","title":{"rendered":"\u4e8c\u53c9\u6811\u7684\u904d\u5386"},"content":{"rendered":"

1 \u6570\u636e\u7ed3\u6784<\/h3>\n

1.1 C++<\/h4>\n
struct TreeNode\n{\n    int val;\n    struct TreeNode *left;\n    struct TreeNode *right;\n    TreeNode(int x) : val(x), left(NULL), right(NULL)\n    {\n    }\n};\n<\/code><\/pre>\n
1.2 Java<\/h4>\n
class TreeNode {\n    int val = 0;\n    TreeNode left = null;\n    TreeNode right = null;\n    public TreeNode(int val) {\n        this.val = val;\n    }\n}\n<\/code><\/pre>\n
2 \u9012\u5f52\u904d\u5386<\/h3>\n
2.1 \u9012\u5f52\u524d\u5e8f\u904d\u5386<\/h4>\n
\u904d\u5386\u987a\u5e8f\uff1a\u4e2d\u3001\u5de6\u3001\u53f3<\/p>\n
2.1.1 C++<\/h5>\n
void show(TreeNode *root)\n{\n    if (!root)\n        return;\n    cout << root->val << \" \";\n    show(root->left);\n    show(root->right);\n}\n<\/code><\/pre>\n
2.1.2 Java<\/h5>\n
public static void show(TreeNode root) {\n    if (root == null)\n        return;\n    System.out.print(root.val + \" \");\n    show(root.left);\n    show(root.right);\n}\n<\/code><\/pre>\n
2.2 \u9012\u5f52\u4e2d\u5e8f\u904d\u5386<\/h4>\n
\u904d\u5386\u987a\u5e8f\uff1a\u5de6\u3001\u4e2d\u3001\u53f3<\/p>\n
2.2.1 C++<\/h5>\n
void show(TreeNode *root)\n{\n    if (!root)\n        return;\n    show(root->left);\n    cout << root->val << \" \";\n    show(root->right);\n}\n<\/code><\/pre>\n
2.2.2 Java<\/h5>\n
public static void show(TreeNode root) {\n    if (root == null)\n        return;\n    show(root.left);\n    System.out.print(root.val + \" \");\n    show(root.right);\n}\n<\/code><\/pre>\n
2.3 \u9012\u5f52\u540e\u5e8f\u904d\u5386<\/h4>\n
\u904d\u5386\u987a\u5e8f\uff1a\u5de6\u3001\u53f3\u3001\u4e2d<\/p>\n
2.3.1 C++<\/h5>\n
void show(TreeNode *root)\n{\n    if (!root)\n        return;\n    show(root->left);\n    show(root->right);\n    cout << root->val << \" \";\n}\n<\/code><\/pre>\n
2.3.2 Java<\/h5>\n
public static void show(TreeNode root) {\n    if (root == null)\n        return;\n    show(root.left);\n    show(root.right);\n    System.out.print(root.val + \" \");\n}\n<\/code><\/pre>\n
3 \u975e\u9012\u5f52\u904d\u5386<\/h3>\n
\u975e\u9012\u5f52\u904d\u5386\uff0c\u4f7f\u7528\u6808\u6765\u5b9e\u73b0\u3002<\/p>\n
3.1 \u975e\u9012\u5f52\u524d\u5e8f\u904d\u5386<\/h4>\n
\u904d\u5386\u987a\u5e8f\uff1a\u4e2d\u3001\u5de6\u3001\u53f3<\/p>\n
\u8981\u6ce8\u610f\u538b\u6808\u7684\u987a\u5e8f\uff0c\u540e\u538b\u5165\u7684\u4f1a\u5148\u904d\u5386\u3002<\/p>\n
3.1.1 C++<\/h5>\n
void show(TreeNode *root)\n{\n    stack<TreeNode *> s;\n    s.push(root);\n    while (!s.empty())\n    {\n        TreeNode *p = s.top();\n        s.pop();\n        if (p)\n        {\n            cout << p->val << \" \";\n            s.push(p->right);\n            s.push(p->left);\n        }\n    }\n}\n<\/code><\/pre>\n
3.1.2 Java<\/h5>\n
public static void show(TreeNode root) {\n    Stack<TreeNode> s = new Stack<>();\n    s.push(root);\n    while (!s.empty()) {\n        TreeNode p = s.pop();\n        if (p != null) {\n            System.out.print(p.val + \" \");\n            s.push(p.right);\n            s.push(p.left);\n        }\n    }\n}\n<\/code><\/pre>\n
3.2 \u975e\u9012\u5f52\u4e2d\u5e8f\u904d\u5386<\/h4>\n
\u904d\u5386\u987a\u5e8f\uff1a\u5de6\u3001\u4e2d\u3001\u53f3<\/p>\n
\u4e3b\u8981\u601d\u60f3\uff1a\u5148\u5c06p<\/code>\u6307\u5411root<\/code>\uff0c\u7136\u540e\u8fdb\u884c\u5faa\u73af
\n1. \u5982\u679cp<\/code>\u4e0d\u4e3a\u7a7a\uff0c\u5c06p<\/code>\u538b\u5165\u6808\u4e2d\uff0c\u6267\u884cp = p->left<\/code>\u3002
\n2. \u5982\u679cp<\/code>\u4e3a\u7a7a\uff0c\u4ece\u6808\u9876\u53d6\u51fa\u5143\u7d20\u8d4b\u503c\u7ed9p<\/code>\uff0c\u8f93\u51fap<\/code>\u5bf9\u5e94\u7684\u503c\uff0c\u6267\u884cp = p->right<\/code>\u3002<\/p>\n
\u7b97\u6cd5\u7684\u96be\u70b9\u5728\u4e8e\u5982\u4f55\u9632\u6b62\u91cd\u590d\u538b\u6808\u3002<\/p>\n
3.2.1 C++<\/h5>\n
void show(TreeNode *root)\n{\n    stack<TreeNode *> s;\n    TreeNode *p = root;\n    while (p || !s.empty())\n    {\n        if (p)\n        {\n            s.push(p);\n            p = p->left;\n        }\n        else\n        {\n            p = s.top();\n            s.pop();\n            cout << p->val << \" \";\n            p = p->right;\n        }\n    }\n}\n<\/code><\/pre>\n
3.2.2 Java<\/h5>\n
public static void show(TreeNode root) {\n    Stack<TreeNode> s = new Stack<>();\n    TreeNode p = root;\n    while (p != null || !s.empty()) {\n        if (p != null) {\n            s.push(p);\n            p = p.left;\n        } else {\n            p = s.pop();\n            System.out.print(p.val + \" \");\n            p = p.right;\n        }\n    }\n}\n<\/code><\/pre>\n
3.3 \u975e\u9012\u5f52\u540e\u5e8f\u904d\u5386<\/h4>\n
\u904d\u5386\u987a\u5e8f\uff1a\u5de6\u3001\u53f3\u3001\u4e2d<\/p>\n
\u4e3b\u8981\u601d\u60f3\uff1a\u5148\u8fdb\u884c\u4e2d\u3001\u53f3\u3001\u5de6<\/code>\u7684\u904d\u5386\uff0c\u7c7b\u4f3c\u524d\u5e8f\u904d\u5386\uff0c\u7136\u540e\u5c06\u7ed3\u679c\u9006\u5e8f\u8f93\u51fa\u5373\u53ef\u3002
\nhttps:\/\/leetcode-cn.com\/problems\/binary-tree-postorder-traversal\/<\/a><\/p>\n
3.3.1 C++<\/h5>\n
vector<int> postorderTraversal(TreeNode *root)\n{\n    vector<int> v, ans;\n    stack<TreeNode *> s;\n    s.push(root);\n    while (!s.empty())\n    {\n        TreeNode *p = s.top();\n        s.pop();\n        if (p)\n        {\n            v.push_back(p->val);\n            s.push(p->left);\n            s.push(p->right);\n        }\n    }\n    ans = vector<int>(v.rbegin(), v.rend());\n    return ans;\n}\n<\/code><\/pre>\n
3.3.2 Java<\/h5>\n
class Solution {\n    public List<Integer> postorderTraversal(TreeNode root) {\n        ArrayList<Integer> ans = new ArrayList<>();\n        Stack<TreeNode> s = new Stack<>();\n        s.push(root);\n        while (!s.empty()) {\n            TreeNode p = s.pop();\n            if (p != null) {\n                ans.add(p.val);\n                s.push(p.left);\n                s.push(p.right);\n            }\n        }\n        Collections.reverse(ans);\/\/ \u9006\u5e8f\n        return ans;\n    }\n}\n<\/code><\/pre>\n
4 \u5c42\u6b21\u904d\u5386<\/h3>\n
\u5c42\u6b21\u904d\u5386\u662f\u4e00\u5c42\u4e00\u5c42\u7684\u904d\u5386\uff0c\u6bcf\u4e00\u5c42\u4ece\u5de6\u5230\u53f3\u904d\u5386\u3002\u501f\u52a9\u961f\u5217\u7684\u5148\u8fdb\u5148\u51fa\u7684\u7279\u6027\u6765\u5b9e\u73b0\u3002<\/p>\n
4.1 C++<\/h5>\n
void show(TreeNode *root)\n{\n    queue<TreeNode *> q;\n    q.push(root);\n    while (!q.empty())\n    {\n        TreeNode *p = q.front();\n        q.pop();\n        if (p)\n        {\n            cout << p->val << \" \";\n            q.push(p->left);\n            q.push(p->right);\n        }\n    }\n}\n<\/code><\/pre>\n
4.2 Java<\/h5>\n
public static void show(TreeNode root) {\n    Queue<TreeNode> q = new LinkedList<>();\n    q.add(root);\n    while (!q.isEmpty()) {\n        TreeNode p = q.poll();\n        if (p != null) {\n            System.out.print(p.val + \" \");\n            q.add(p.left);\n            q.add(p.right);\n        }\n    }\n}\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
1 \u6570\u636e\u7ed3\u6784 1.1 C++ struct TreeNode { int val; struct TreeNo […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[33,52],"class_list":["post-740","post","type-post","status-publish","format-standard","hentry","category-note","tag-33","tag-52"],"_links":{"self":[{"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/posts\/740","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=740"}],"version-history":[{"count":0,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/posts\/740\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=740"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=740"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=740"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}