C++实现LeetCode(145.二叉树的后序遍历)

[LeetCode] 145. Binary Tree Postorder Traversal 二叉树的后序遍历

Given a binary tree, return the postorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},

   1
\
2
/
3

return [3,2,1].

Note: Recursive solution is trivial, could you do it iteratively?

经典题目,求二叉树的后序遍历的非递归方法,跟前序,中序,层序一样都需要用到栈,后序的顺序是左-右-根,所以当一个结点值被取出来时,它的左右子结点要么不存在,要么已经被访问过了。先将根结点压入栈,然后定义一个辅助结点 head,while 循环的条件是栈不为空,在循环中,首先将栈顶结点t取出来,如果栈顶结点没有左右子结点,或者其左子结点是 head,或者其右子结点是 head 的情况下。将栈顶结点值加入结果 res 中,并将栈顶元素移出栈,然后将 head 指向栈顶元素;否则的话就看如果右子结点不为空,将其加入栈,再看左子结点不为空的话,就加入栈,注意这里先右后左的顺序是因为栈的后入先出的特点,可以使得左子结点先被处理。下面来看为什么是这三个条件呢,首先如果栈顶元素如果没有左右子结点的话,说明其是叶结点,而且入栈顺序保证了左子结点先被处理,所以此时的结点值就可以直接加入结果 res 了,然后移出栈,将 head 指向这个叶结点,这样的话 head 每次就是指向前一个处理过并且加入结果 res 的结点,那么如果栈顶结点的左子结点或者右子结点是 head 的话,说明其子结点已经加入结果 res 了,那么就可以处理当前结点了。

看到这里,大家可能对 head 的作用,以及为何要初始化为 root,还不是很清楚,这里再解释一下。head 是指向上一个被遍历完成的结点,由于后序遍历的顺序是左-右-根,所以一定会一直将结点压入栈,一直到把最左子结点(或是最左子结点的最右子结点)压入栈后,开始进行处理。一旦开始处理了,head 就会被重新赋值。所以 head 初始化值并没有太大的影响,唯一要注意的是不能初始化为空,因为在判断是否打印出当前结点时除了判断是否是叶结点,还要看 head 是否指向其左右子结点,如果 head 指向左子结点,那么右子结点一定为空,因为入栈顺序是根-右-左,不存在右子结点还没处理,就直接去处理根结点了的情况。若 head 指向右子结点,则是正常的左-右-根的处理顺序。那么回过头来在看,若 head 初始化为空,且此时正好左子结点不存在,那么在压入根结点时,head 和左子结点相等就成立了,此时就直接打印根结点了,明显是错的。所以 head 只要不初始化为空,一切都好说,甚至可以新建一个结点也没问题。将 head 初始化为 root,也可以,就算只有一个 root 结点,那么在判定叶结点时就将 root 打印了,然后就跳出 while 循环了,也不会出错。代码如下:

解法一:

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        if (!root) return {};
        vector<int> res;
        stack<TreeNode*> s{{root}};
        TreeNode *head = root;
        while (!s.empty()) {
            TreeNode *t = s.top();
            if ((!t->left && !t->right) || t->left == head || t->right == head) {
                res.push_back(t->val);
                s.pop();
                head = t;
            } else {
                if (t->right) s.push(t->right);
                if (t->left) s.push(t->left);
            }
        }
        return res;
    }
};

由于后序遍历的顺序是左-右-根,而先序遍历的顺序是根-左-右,二者其实还是很相近的,可以先在先序遍历的方法上做些小改动,使其遍历顺序变为根-右-左,然后翻转一下,就是左-右-根啦,翻转的方法我们使用反向Q,哦不,是反向加入结果 res,每次都在结果 res 的开头加入结点值,而改变先序遍历的顺序就只要该遍历一下入栈顺序,先左后右,这样出栈处理的时候就是先右后左啦,参见代码如下:

解法二:

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        if (!root) return {};
        vector<int> res;
        stack<TreeNode*> s{{root}};
        while (!s.empty()) {
            TreeNode *t = s.top(); s.pop();
            res.insert(res.begin(), t->val);
            if (t->left) s.push(t->left);
            if (t->right) s.push(t->right);
        }
        return res;
    }
};

那么在 Binary Tree Preorder Traversal 中的解法二也可以改动一下变成后序遍历,改动的思路跟上面的解法一样,都是先将先序遍历的根-左-右顺序变为根-右-左,再翻转变为后序遍历的左-右-根,翻转还是改变结果 res 的加入顺序,然后把更新辅助结点p的左右顺序换一下即可,代码如下:

解法三:

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> s;
        TreeNode *p = root;
        while (!s.empty() || p) {
            if (p) {
                s.push(p);
                res.insert(res.begin(), p->val);
                p = p->right;
            } else {
                TreeNode *t = s.top(); s.pop();
                p = t->left;
            }
        }
        return res;
    }
};

论坛上还有一种双栈的解法,其实本质上跟解法二没什么区别,都是利用了改变先序遍历的顺序来实现后序遍历的,参见代码如下:

解法四:

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        if (!root) return {};
        vector<int> res;
        stack<TreeNode*> s1, s2;
        s1.push(root);
        while (!s1.empty()) {
            TreeNode *t = s1.top(); s1.pop();
            s2.push(t);
            if (t->left) s1.push(t->left);
            if (t->right) s1.push(t->right);
        }
        while (!s2.empty()) {
            res.push_back(s2.top()->val); s2.pop();
        }
        return res;
    }
};

到此这篇关于C++实现LeetCode(145.二叉树的后序遍历)的文章就介绍到这了,更多相关C++实现二叉树的后序遍历内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

时间: 2021-07-16

C++实现LeetCode(137.单独的数字之二)

[LeetCode] 137. Single Number II 单独的数字之二 Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one. Note: Your algorithm should have a linear runtime complexity. Could you

C++实现LeetCode(96.独一无二的二叉搜索树)

[LeetCode] 96. Unique Binary Search Trees 独一无二的二叉搜索树 Given n, how many structurally unique BST's (binary search trees) that store values 1 ... n? Example: Input: 3 Output: 5 Explanation: Given n = 3, there are a total of 5 unique BST's: 1         3  

C++实现LeetCode(95.独一无二的二叉搜索树之二)

[LeetCode] 95. Unique Binary Search Trees II 独一无二的二叉搜索树之二 Given an integer n, generate all structurally unique BST's (binary search trees) that store values 1 ... n. Example: Input: 3 Output: [ [1,null,3,2], [3,2,null,1], [3,1,null,null,2], [2,1,3],

C++实现LeetCode(312.打气球游戏)

[LeetCode] 312. Burst Balloons 打气球游戏 Given n balloons, indexed from 0 to n-1. Each balloon is painted with a number on it represented by array nums. You are asked to burst all the balloons. If the you burst balloon iyou will get nums[left] * nums[i]

C++实现LeetCode(93.复原IP地址)

[LeetCode] 93.Restore IP Addresses 复原IP地址 Given a string containing only digits, restore it by returning all possible valid IP address combinations. Example: Input: "25525511135" Output: ["255.255.11.135", "255.255.111.35"] 这

C++实现LeetCode(241.添加括号的不同方式)

[LeetCode] 241. Different Ways to Add Parentheses 添加括号的不同方式 Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +, - and *. Exampl

C++实现LeetCode(97.交织相错的字符串)

[LeetCode] 97.Interleaving String 交织相错的字符串 Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2. Example 1: Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac" Output: true Example 2: Input: s1 = &quo

C++实现LeetCode(91.解码方法)

[LeetCode] 91. Decode Ways 解码方法 A message containing letters from A-Z is being encoded to numbers using the following mapping: 'A' -> 1 'B' -> 2 ... 'Z' -> 26 Given a non-empty string containing only digits, determine the total number of ways to

Python中json格式数据的编码与解码方法详解

本文实例讲述了Python中json格式数据的编码与解码方法.分享给大家供大家参考,具体如下: python从2.6版本开始内置了json数据格式的处理方法. 1.json格式数据编码 在python中,json数据格式编码使用json.dumps方法. #!/usr/bin/env python #coding=utf8 import json users = [{'name': 'tom', 'age': 22}, {'name': 'anny', 'age': 18}] #元组对象也可以

Python3内置模块之json编解码方法小结

Python3内置模块之json编解码方法小结 Python3中我们利用内置模块 json 解码和编码 JSON对象 ,JSON(JavaScript Object Notation)是指定 RFC 7159(废弃了RFC 4627)和 ECMA-404是一种轻量级数据交换格式,受 JavaScript对象文字语法的启发 (虽然它不是JavaScript 1的严格子集).下面为Python对象-->JSON对象的对照关系表. dumps编码 我们利用 dumps 将Python对象编码为 JSO

Java JDK1.7对字符串的BASE64编码解码方法

如下所示: package cn.itcast; import java.io.IOException; import java.io.UnsupportedEncodingException; import org.junit.Test; import sun.misc.BASE64Decoder; /* * @author soto * BASE64编码 解码 * */ public class Demo1 { @Test public void fun1() throws IOExcept

vscode+leetcode环境配置方法

前言 之前安装anaconda3的时候,选择了同时安装vscode,但从来没有正式去接触过它.最近,偶然想到看看leetcode,发现在vscode上搞leetcode很方便,于是就开始倒腾起来了. vscode配置 如何安装我就不详述了,win/ubuntu下的安装可参见我的博客: vscode+python+c++ 我现在的vscode的版本是:1.43.1 需要安装的插件有: anaconda extension pack: 支持非python官方的三方库code runner:F5快捷运

Python3内置模块之json编解码方法小结【推荐】

Python3中我们利用内置模块 json 解码和编码 JSON对象 ,JSON(JavaScript Object Notation)是指定 RFC 7159(废弃了RFC 4627)和 ECMA-404是一种轻量级数据交换格式,受 JavaScript对象文字语法的启发 (虽然它不是JavaScript 1的严格子集).下面为Python对象-->JSON对象的对照关系表. dumps编码 我们利用 dumps 将Python对象编码为 JSON对象 ,当然 dumps 只完成了序列化为st

Python JSON常用编解码方法代码实例

概念 JSON(JavaScript Object Notation) 是一种轻量级的数据交换格式,易于人阅读和编写.在日常的工作中,应用范围极其广泛.这里就介绍python下它的两种编解码方法: 使用json函数 使用 JSON 函数需要导入 json 库:import json.函数含义: 源码解析: # coding= utf-8 #!/usr/bin/python import json import sys data = {"username":"测试",

Python3内置模块之base64编解码方法详解

概述 Base64 是网络上最常见的用于传输 8Bit 字节码的编码方式之一,Base64 就是一种基于 64 个可打印字符来表示二进制数据的方法.可查看 RFC2045 - RFC2049,上面有 MIME 的详细规范.Base64 编码是从二进制到字符的过程,可用于在 HTTP 环境下传递较长的标识信息.比如使二进制数据可以作为电子邮件的内容正确地发送,用作 URL 的一部分,或者作为 HTTP POST 请求的一部分. 即 base64 其实不能归属密码领域,作用也不是用于加密,它是一种编

Javascript下的urlencode编码解码方法附decodeURIComponent

关于在ASP(Server.UrlEncode).PHP(urlencode())函数编码结果,或是经过asp.php等动态语言直接写入COOKIES的中文字符,用JS读取的时候,都会碰到一个编码的问题,那就是最终字符串被urlencode编码了,而又时有需要从JS在客户端去读取这些数据. 而本文,就大概说说如何在js中通过系统自带的函数去解决这个问题. 而相信碰到过此问题的朋友应该都有所了解,目前网络上流行一些js下的自定义函数去解决这个问题,如说vbscript(URLDecode()).j

Python3 JSON编码解码方法详解

JSON(JavaScript Object Notation)是一种轻量级的数据交换格式,它基于ECMAScript的一个子集. JSON采用完全独立于语言的文本格式,这些特性使JSON成为理想的数据交换格式,易于人阅读和编写,同时也易于机器解析和生成,在接口数据开发和传输中非常常用. Python3中我们利用内置模块json解码和编码JSON对象.json模块提供了四个功能:dumps.dump.loads.load dumps 把数据类型转换成字符串 dump 把数据类型转换成字符串并存储

java中文乱码之解决URL中文乱码问题的方法

我们主要通过两种形式提交向服务器发送请求:URL.表单.而表单形式一般都不会出现乱码问题,乱码问题主要是在URL上面.通过前面几篇博客的介绍我们知道URL向服务器发送请求编码过程实在是实在太混乱了.不同的操作系统.不同的浏览器.不同的网页字符集,将导致完全不同的编码结果.如果程序员要把每一种结果都考虑进去,是不是太恐怖了?有没有办法,能够保证客户端只用一种编码方法向服务器发出请求? 有!这里我主要提供以下几种方法 一.javascript 使用javascript编码不给浏览器插手的机会,编码之