leetcode 145. Binary Tree Postorder Traversal 二叉树后续遍历

快来打我* 2022-06-08 06:24 180阅读 0赞

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\].

就是考察后序遍历的非递归形式，直接上代码吧！

**注意二叉树的前序、中序、后序遍历的递归和非递归都必须掌握。**

代码如下：

import java.util.ArrayList;
    import java.util.List;
    import java.util.Stack;
    
    /*class TreeNode 
    {
         int val;
         TreeNode left;
         TreeNode right;
         TreeNode(int x) { val = x; }
    }*/
    
    
    public class Solution
    {
        List<Integer> res=new ArrayList<>();
        public List<Integer> postorderTraversal(TreeNode root) 
        {
            if(root==null)
                return res;
            //postOrder(root);
            postOrderByIterator(root);
            return res;
        }
    
        // 中序遍历
        /*
         * Root表示下一个要处理的结点，初始化为根结点，Per表示上一次刚刚输出过的结点。
         * ，Per的作用是对有孩子的结点进行判断，由于算法特性，每次到某个结点时，
         * 其左子树都输出过了，此时只要判断Pre是否是当前结点的右孩子，如果不是，
         * 那么说明其右子树没走过，那么Root=当前结点的右子树，否则就是刚刚输出了
         * 当前结点的右孩子，由于是后序，其右子树也必定都输出过了，此时只要输出当前结点，
         * 更新Pre就好了。
         * 
           while(Root不为空 || 栈不为空) 
           {
             if(Root不为空) // 一路向左
                Root入栈
                Root=Root->left_child
             else { // 此时栈顶元素的左子树都输出过了
                 Root = 栈顶元素
                 if(Root有右孩子 && Pre不等于Root的右孩子) // 此时栈顶元素的右子树还没输出
                     Root=Root->right
                 else // 此时栈顶元素的左右子树都输出过了
                                                输出栈顶元素
                     Pre = 栈顶元素
                                                  栈顶元素出栈  
                      iter设置为null            
                 }
             }
         * */
        void postOrderByIterator(TreeNode root) 
        {
            Stack<TreeNode> myStack=new Stack<>();
            TreeNode iter=root;
            TreeNode pre=null;
    
            while(iter!=null || myStack.isEmpty()==false)
            {
                if(iter!=null)
                {
                    myStack.push(iter);
                    iter=iter.left;
                }else
                {
                    iter=myStack.peek();
                    if(iter.right!=null && iter.right!=pre)
                        iter=iter.right;
                    else
                    {
                        res.add(iter.val);
                        pre=iter;
                        myStack.pop();
                        //这个要设置为null
                        iter=null;
                    }
                }
            }
        }    
    
        // 中序遍历
        /*
         *    前序中的Root主要作为中间变量使用。这里的Root的意义是下一个要进栈的结点，初始值为根结点。
              while (Root不为空 || 栈不为空) 
              {
                 if(Root不为空) // 一路向左入栈 
                    Root入栈
                    Root=Root->left_child。
                 else // 栈顶元素的左子树都输出过了
                                             输出栈顶元素
                   Root=栈顶元素->right_child
                                           栈顶元素出栈。
              } 
         * */
        void InOrderByIterator(TreeNode root) 
        {
            Stack<TreeNode> myStack=new Stack<>();
            TreeNode iter=root;
    
            while(iter!=null || myStack.isEmpty()==false)
            {
                if(iter!=null)
                {
                    myStack.push(iter);
                    iter=iter.left;
                }else
                {
                    TreeNode top=myStack.peek();
                    myStack.pop();
                    res.add(top.val);
                    iter=top.right;
                }
            }
        }
    
    
        //递归 后序遍历
        void postOrder(TreeNode root) 
        {
            if(root==null)
                return;
            else
            {
                postOrder(root.left);
                postOrder(root.right);
                res.add(root.val);
            }
    
        }
    }

下面是C++的做法，就是一个DFS递归遍历

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    #include <iomanip>
    #include <cstdlib>
    #include <ctime>
    
    using namespace std;
    
    
    
    /*
    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)
        {
            vector<int> res;
            if (root == NULL)
                return res;
    
            stack<TreeNode*> skt;
            skt.push(root);
            TreeNode* pre = NULL, *cur = NULL;
            while (cur!=NULL && skt.empty()==false)
            {
                cur = skt.top();
                if (cur->left == NULL && cur->right == NULL
                    || (pre != NULL && (pre == cur->left || pre == cur->right)))
                {
                    res.push_back(cur->val);
                    skt.pop();
                    pre = cur;
                }
                else
                {
                    if (cur->right != NULL)
                        skt.push(cur->right);
                    if (cur->left != NULL)
                        skt.push(cur->left);
                }
            }
            return res;
        }
    };