发表于 | 更新于 | 分类于

题目

hareyukai way

递归实现 + 参数传迭代器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {        
        return buildTree(rbegin(inorder), rend(inorder),
                         rbegin(postorder), rend(postorder));
    }
    
    template<typename RandomIt>
    TreeNode* buildTree(RandomIt in_rfirst, RandomIt in_rlast,
                        RandomIt post_rfirst, RandomIt post_rlast) {
        if (in_rfirst == in_rlast) return nullptr;
        if (post_rfirst == post_rlast) return nullptr;
        
        auto root = new TreeNode(*post_rfirst);
        
        auto inRootRPos = find(in_rfirst, in_rlast, *post_rfirst);
        auto RightSize = distance(in_rfirst, inRootRPos);
        
        root->right = buildTree(in_rfirst,
                                next(in_rfirst, RightSize),
                                next(post_rfirst),
                                next(post_rfirst, RightSize + 1));
        root->left = buildTree(next(inRootRPos),
                               in_rlast,
                               next(post_rfirst, RightSize + 1),
                               post_rlast);
        return root;
    }
};

简单修改了一下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
using It = vector<int>::reverse_iterator;

class Solution {
private:
    TreeNode* buildTree(It inFir, It inLast, It postFir, It postLast)
    {
        if (inFir == inLast || postFir == postLast) return nullptr;

        auto root = new TreeNode(*postFir);

        auto inRootPos = find(inFir, inLast, *postFir);
        auto RightSize = distance(inFir, inRootPos);

        root->right = buildTree(inFir, next(inFir, RightSize), next(postFir), next(postFir, RightSize + 1));
        root->left = buildTree(next(inRootPos), inLast, next(postFir, RightSize + 1), postLast);

        return root;
    }
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) 
    {
        return buildTree(inorder.rbegin(), inorder.rend(), postorder.rbegin(), postorder.rend());
    }
};

发表于 | 更新于 | 分类于

题目

当当喵 way

dfs遍历 + isLeft来标注当前节点状态即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    int sum = 0;
    void getSum(TreeNode* root, bool isLeft)
    {
        if (!root)  return;

        if (isLeft && !root->left && !root->right)
        {
            sum += root->val;
        }
        else
        {
            getSum(root->left, true);
            getSum(root->right, false);
        }
    }
public:
    int sumOfLeftLeaves(TreeNode* root) 
    {
        getSum(root, false);

        return sum;    
    }
};

References

https://leetcode-cn.com/problems/sum-of-left-leaves/solution/chao-ji-rong-yi-li-jie-qi-shi-he-qiu-quan-lu-jing-/

发表于 | 更新于 | 分类于

题目

My way

序列化 + 重复子序列DP解法 + 反序列化回去时找到对应子树root结点

感觉代价过高，而且在反序列化回去找到对应结点时会很麻烦。

yushinan

序列化+hash取出重复子树的头结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
  vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
    unordered_map<string, int> counts;
    vector<TreeNode*> ans;
    serialize(root, counts, ans);
    return ans;
  }
private:
  string serialize(TreeNode* root, 
    unordered_map<string, int>& counts,
    vector<TreeNode*>& ans) {
    if (!root) return "#";
    string key = to_string(root->val) + "," 
        + serialize(root->left, counts, ans) + "," 
        + serialize(root->right, counts, ans);
    if (++counts[key] == 2)
      ans.push_back(root);
    return key;
  }
};

*yuguorui

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
struct SubTreeCount
{
	TreeNode* root;
	int count;

};

class Solution {
public:
	unordered_map<size_t, SubTreeCount> dict;
	hash<string> hasher;
	vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
		serialize(root);
		vector<TreeNode*> res;
		for(auto const& item: dict) {
			if (item.second.count > 1) {
				res.push_back(item.second.root);
			}
		}
		return res;
	}

	size_t serialize(TreeNode* root) {
		if (root == NULL) return hasher("[]");
		char buf[2048];
		snprintf(buf, 2048, "[%d,%d,%d]", root->val, serialize(root->left), serialize(root->right));
		size_t res = hasher(buf);

		if (dict.count(res) == 0) {
			dict.insert(pair<size_t, SubTreeCount>(res, {root, 1}));
		} else {
			dict[res].count++;
		}
		return res;
	}
};
  • 利用了hash<string>后结果，作为判断这一子序列是否出现过的情况/有重复子串的情况；
  • 用snprintf的IO流来生成对应序列化结果。

总结

  • 对整棵树中，每一颗子树都进行序列化，并利用unordered_map得到每个子树的序列化结果是否重复
  • 对于序列化路径有：node.path = node.val + node.left.path + node.right.path
  • 这里的序列化，可以不用序列化null

Reference

https://leetcode-cn.com/problems/find-duplicate-subtrees/solution/simple-solution-by-yushinan-2/

发表于 | 更新于 | 分类于

题目

官方

递归实现

考虑4种情况：

  1. 如果当前节点有两个孩子，那我们在递归时，需要在两个孩子的结果外都加上一层括号；
  2. 如果当前节点没有孩子，那我们不需要在节点后面加上任何括号；
  3. 如果当前节点只有左孩子，那我们在递归时，只需要在左孩子的结果外加上一层括号，而不需要给右孩子加上任何括号；
  4. 如果当前节点只有右孩子，那我们在递归时，需要先加上一层空的括号 () 表示左孩子为空，再对右孩子进行递归，并在结果外加上一层括号。
java实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public String tree2str(TreeNode t) {
        if(t==null)
            return "";
        if(t.left==null && t.right==null)
            return t.val+"";
        if(t.right==null)
            return t.val+"("+tree2str(t.left)+")";
        return t.val+"("+tree2str(t.left)+")("+tree2str(t.right)+")";   
    }
}

改下排版

1
2
3
4
5
6
7
8
9
public class Solution {
    public String tree2str(TreeNode t) {
    	if (!t)		return "";
        if (!t.left && !t.right)	return t.val + "";
        if (!t.right)	return t.val + "(" + tree2str(t.left) + ")";
        
        return t.val+"("+tree2str(t.left)+")("+tree2str(t.right)+")";  
    }
}
C++实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    string tree2str(TreeNode* t) 
    {
    	if (!t)	return "";
        if (!t->left && !t->right)	return to_string(t->val);
        if (!t->right)	return to_string(t->val) + "(" + tree2str(t->left) + ")";
        return	to_string(t->val) + "(" + tree2str(t->left) + ")(" + tree2str(t->right) + ")";
    }
};

非递归手动压栈

  • 因为要保存括号，所以需要一个集合存储所有遍历过的节点
  • 它没有子节点，什么都不做
  • 有两个节点，右孩子先入栈，再左孩子入栈，保证先序遍历顺序
  • 如果只有左孩子，则左孩子入栈
  • 如果只有右孩子，则末尾添加一个()后，再将右孩子入栈
java实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public class Solution {
    public String tree2str(TreeNode t) {
        if (t == null)
            return "";
        Stack < TreeNode > stack = new Stack < > ();
        stack.push(t);
        Set < TreeNode > visited = new HashSet < > ();
        StringBuilder s = new StringBuilder();
        while (!stack.isEmpty()) {
            t = stack.peek();
            if (visited.contains(t)) {
                stack.pop();
                s.append(")");
            } else {
                visited.add(t);
                s.append("(" + t.val);
                if (t.left == null && t.right != null)
                    s.append("()");
                if (t.right != null)
                    stack.push(t.right);
                if (t.left != null)
                    stack.push(t.left);
            }
        }
        return s.substring(1, s.length() - 1);
    }
}
C++实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    string tree2str(TreeNode* t) 
    {
		if (!t)	return "";
        
        string str = "";
        set<TreeNode*> visited;
        stack<TreeNode*> s;
        s.push(t);
       	
        
        while (!s.empty())
        {
            t = s.top();
            
            if (visited.find(t) != visited.end())
            {
            	s.pop();
                str += ")";
			}
            else
            {
                visited.insert(t);
                str += "(" + to_string(t->val);
                
                if (!t->left && t->right)	str += "()";
                if (t->right)	s.push(t->right);
                if (t->left)	s.push(t->left);
            }
        }
        return str.substr(1, str.size() - 2);
    }
};

\[ \begin{align*} & e.g. \\ & INPUT: & [1,2,3,4] \\ & OUTPUT: & (1\\ & & (1(2\\ & &(1(2(4\\ & &(1(2(4)\\ & &(1(2(4)) \\ & &(1(2(4))(3\\ & &(1(2(4))(3)\\ & &(1(2(4))(3))\\ \end{align*} \]

MrHuang

  • 用stringstream代替string
  • 用lambda表达式代替函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    string tree2str(TreeNode* t) {
        if(t==nullptr)
            return "";
        stringstream ss;
        function<void(TreeNode*)> helper = [&ss, &helper](TreeNode* t){
            ss<<t->val;
            if(t->left==nullptr){
                if(t->right!=nullptr){
                    ss<<"()(";
                    helper(t->right);
                    ss<<')';
                }
            }
            else if(t->right==nullptr){
                ss<<'(';
                helper(t->left);
                ss<<')';
            }
            else{
                ss<<'(';
                helper(t->left);
                ss<<")(";
                helper(t->right);
                ss<<')';
            }
        };
        helper(t);
        string s;
        ss>>s;
        return s;
    }
};

References

https://leetcode-cn.com/problems/construct-string-from-binary-tree/solution/gen-ju-er-cha-shu-chuang-jian-zi-fu-chuan-by-leetc/

https://leetcode-cn.com/problems/construct-string-from-binary-tree/solution/cgao-xiao-di-cun-fang-fa-by-mrhuang-3/

https://stackoverflow.com/questions/1701067/how-to-check-that-an-element-is-in-a-stdset

发表于 | 更新于 | 分类于

题目

My way

手动队列序列化 + 手动出队反序列化

因为C++ STL没有split, boost里面有。

所以考虑自己实现一个split函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector<string> splitStrToStrArray(string s, string delimiter)
{
	string token;
	vector<string> vs;
    
    while(token != s){
      token = s.substr(0,s.find_first_of(delimiter));
      s = s.substr(s.find_first_of(delimiter) + 1);
      //printf("%s ",token.c_str());
      vs.push_back(token);
    }

	return vs;
}

根据题意要求写了个如下的出来，包括测试用例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>

using namespace std;

struct TreeNode {
      int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 };

class Codec {
private:
vector<string> splitStrToStrArray(const string& s, const string& delimiter)
{
    // remove "[" and "]"
    string str = s.substr(1, s.size() - 2);
	string token;
	vector<string> vs;
    
    while(token != str){
      token = str.substr(0,str.find_first_of(delimiter));
      str = str.substr(str.find_first_of(delimiter) + 1);
      //printf("%s ",token.c_str());
      vs.push_back(token);
    }
	return vs;
}

TreeNode* genNodebyStr(const string& s)
{
    if (s == "null")    return nullptr;
    
    TreeNode* node = new TreeNode(stoi(s));
    return node;
}

public:
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) 
    {
        if (!root)  return "[null,]";

        string res = to_string(root->val) + ",";
        deque<TreeNode*> q;
        q.push_back(root);

        while (!q.empty())
        {
            auto top = q.front();    q.pop_front();
            if (top->left)     
            {
                q.push_back(top->left);     
                res += to_string(top->left->val) + ",";
            }
            else
            {
                res += "null,";
            }

            if (top->right)     
            {
                q.push_back(top->right);    
                res += to_string(top->right->val) + ",";
            }
            else
            {
                res += "null,";
            }
        }
        res = "[" + res + "]";
        
//        cout << res << endl;
        return res;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(const string& data) 
    {
        vector<string> vs = splitStrToStrArray(data, ",");
        int index = 0;
        TreeNode* root = genNodebyStr(vs[index++]);
        deque<TreeNode*> q;

        if (!root)  q.push_back(root);
        TreeNode* node = nullptr;

        while(!q.empty())
        {
            node = q.front(); q.pop_front();
            node->left = genNodebyStr(vs[index++]);
            node->right = genNodebyStr(vs[index++]);

            if (node->left)     q.push_back(node->left);
            if (node->right)    q.push_back(node->right);
        }

        return root;
    }
};

// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));


int main(void)
{
    TreeNode* root = new TreeNode(1);
    TreeNode* n1 = new TreeNode(2);
    TreeNode* n2 = new TreeNode(3);
    TreeNode* n4 = new TreeNode(4);
    TreeNode* n5 = new TreeNode(5);
    
    root->left = n1;    root->right = n2;
    n2->left = n4;      n2->right = n5;
    
    
    
    
    
    Codec c;
    c.deserialize(c.serialize(root));
    
    cout << stoi("12") << endl;
    return 0;
}

但是发现这个过不了测试用例，然后输出后发现为

[1,2,3,null,null,4,5,null,null,null,null,]

而不是要求的:

[1,2,3,null,null,4,5]

所以应该是说，最下面一层叶子要序列化它的null孩子。

Ting Yu way

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Codec {
public:
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) 
    {
        ostringstream out;
        serialize(root,out);
        return out.str();
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) 
    {
        istringstream in(data);
        return deserialize(in);
    }
private:
    void serialize(TreeNode* root,ostringstream& out)
    {
        if(root)
        {
            out<<root->val<<' ';
            serialize(root->left,out);
            serialize(root->right,out);
        }else
        {
            // 这里一定要带着空格，因为在输入的时候用来表示当前输入结束
            out<<"# ";
        }
        
    }

    TreeNode* deserialize(istringstream& in)
    {
        string val;
        in>>val;
        if(val=="#")
        {
            return nullptr;
        }
        TreeNode* root=new TreeNode(stoi(val));
        root->left=deserialize(in);
        root->right=deserialize(in);
        return root;
    }
};

官方

Binary Search Tree 的序列化本质上是对其值进行编码，更重要的是对其结构进行编码。

可以遍历树来完成上述任务。众所周知，我们有两个一般策略：

  • 广度优先搜索（BFS） 我们按照高度的顺序从上到下逐级扫描树。更高级别的节点将先于较低级别的节点访问。
  • 深度优先搜索（DFS)
    • 在这个策略中，我们采用深度作为优先顺序，这样我们就可以从一个根开始，一直延伸到某个叶，然后回到根，到达另一个分支。
    • 根据根节点、左节点和右节点之间的相对顺序，可以进一步将DFS策略区分为 preorder、inorder 和 postorder 。

然而，在这个任务中，DFS 策略更适合我们的需要，因为相邻节点之间的链接自然地按顺序编码，这对后面的反序列化任务非常有帮助。

因此，在这个解决方案中，我们用 preorder DFS 策略演示了一个示例。您可以在 leetcode explore上查看有关二叉搜索树的更多教程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
// Serialization
public class Codec {
  public String rserialize(TreeNode root, String str) {
    // Recursive serialization.
    if (root == null) {
      str += "null,";
    } else {
      str += str.valueOf(root.val) + ",";
      str = rserialize(root.left, str);
      str = rserialize(root.right, str);
    }
    return str;
  }

  // Encodes a tree to a single string.
  public String serialize(TreeNode root) {
    return rserialize(root, "");
  }


public TreeNode rdeserialize(List<String> l) {
    // Recursive deserialization.
    if (l.get(0).equals("null")) {
      l.remove(0);
      return null;
    }

    TreeNode root = new TreeNode(Integer.valueOf(l.get(0)));
    l.remove(0);
    root.left = rdeserialize(l);
    root.right = rdeserialize(l);

    return root;
  }

  // Decodes your encoded data to tree.
  public TreeNode deserialize(String data) {
    String[] data_array = data.split(",");
    List<String> data_list = new LinkedList<String>(Arrays.asList(data_array));
    return rdeserialize(data_list);
  }
};

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));

总结

  • 利用sstream里的istringstream和ostringstream来解决字符串相关问题，是我之前没想到的

Reference

https://stackoverflow.com/questions/14265581/parse-split-a-string-in-c-using-string-delimiter-standard-c

https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/solution/c-version-by-zzyuting/

发表于 | 更新于 | 分类于

题目

My way

递归实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    vector<int> vi;
    void helper(TreeNode* root)
    {
        if (!root)  return ;
        helper(root->left); 
        vi.push_back(root->val);
        helper(root->right);
    }

public:
    vector<int> inorderTraversal(TreeNode* root) {
        helper(root);

        return vi;    
    }
};

手动压栈实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    vector<int> vi;

public:
    vector<int> inorderTraversal(TreeNode* root)     
    {
        if (root) 
        {
            stack<TreeNode*> s;

            while(!s.empty() || root)
            {
                if (root)   
                {
                    s.push(root);
                    root = root->left;
                }
                else 
                {
                    root = s.top(); s.pop();
                    vi.push_back(root->val);
                    root = root->right;
                }
            }
            
        }   

        return vi;
    }
};

总结

  • 因为中序遍历是 "左根右"，所以得
    • 先遍历到最左的结点，则这个结点可能是 "左根右"中的 左 或者 根 或者 null
    • 若为 左/根， 则 都需保存它的右孩子(为空/不空)，然后继续考察他的 ”左根右“结构。
    • 若不为null， 则 保存当前结点，且继续往左孩子遍历
    • 若 为null，则 弹栈 并 打印当前栈顶元素值，然后往右孩子遍历

发表于 | 更新于 | 分类于

题目

My way

递归实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    vector<int> vi;
    void helper(TreeNode* root)
    {
        if (!root)  return ;

        helper(root->left);
        helper(root->right);
        vi.push_back(root->val);
    }

public:
    vector<int> postorderTraversal(TreeNode* root) {
        helper(root);

        return vi;
    }
};

非递归手动压栈+逆序输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    vector<int> vi;
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> s;

        if (root)
        {
            s.push(root);

            while(!s.empty())
            {
                auto top = s.top();    s.pop();
                vi.push_back(top->val);

                if (top->left)     s.push(top->left);
                if (top->right)    s.push(top->right);
            }
        }

        return vector<int>(vi.rbegin(), vi.rend());
    }
};

非递归手动压栈 + 辅助变量判断右孩子是否访问过

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> mystack;
        vector<int> ans;
        TreeNode* curr = root;
        TreeNode* pre = NULL;
        
        while(curr || !mystack.empty())
        {
            while(curr)
            {
                mystack.push(curr);
                curr = curr->left;
            }
            curr = mystack.top();
            
            //若右节点已经访问过或者没有右节点  则输出该节点值
            if(!curr->right || pre == curr->right){
                mystack.pop();
                ans.push_back(curr->val);    
                pre = curr;
                curr = NULL;
            }else{
                curr = curr->right;
                pre = NULL;
            }
        }
        return ans;
    }
};

References

https://leetcode-cn.com/problems/binary-tree-postorder-traversal/solution/c-by-jjjjjz-2/

发表于 | 分类于

题目

My way

递归实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    vector<int> vi;
    void helper(TreeNode* root)
    {
        if (!root)  return ;
        vi.push_back(root->val);
        helper(root->left); 
        helper(root->right);
    }
public:
    vector<int> preorderTraversal(TreeNode* root) {
        helper(root);

        return vi;
    }
};

手动压栈实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    vector<int> vi;

public:
    vector<int> preorderTraversal(TreeNode* root) 
    {
        if (root) 
        {
            stack<TreeNode*> s;
            s.push(root);

            while (!s.empty())
            {
                auto top = s.top(); s.pop();
                vi.push_back(top->val);

                if (top->right)    s.push(top->right);
                if (top->left)    s.push(top->left); 
            }
        }   

        return vi;
    }
};

总结

  • 因为前序遍历是 ”根左右“，所以手动入栈的时候是 先右孩子，再左孩子