leetcode 144. Binary Tree Preorder Traversal 二叉树前序遍历 + 深度优先遍历DFS

谁借莪１个温暖的怀抱￠ 2022-06-08 04:58 188阅读 0赞

Given a binary tree, return the preorder traversal of its nodes’ values.

For example:  
Given binary tree \{1,\#,2,3\},  
1  
\\  
2  
/  
3  
return \[1,2,3\].

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

本题考察的是二叉树的前序遍历的非递归实现。

嗯嗯，直接看代码吧！

代码如下：

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>  preorderTraversal(TreeNode root) 
        {
            if(root==null)
                return res;
            else
            {
                //preOrder(root);
                byIteratorPreOrder(root);
                return res;
            }
        }
    
        //前序遍历非递归
        void byIteratorPreOrder(TreeNode root) 
        {
            Stack<TreeNode> myStack=new Stack<>();
            myStack.push(root);
    
            //就是栈顶元素top出栈，然后访问top，然后添加top的子节点
            while(myStack.isEmpty()==false)
            {
                TreeNode top=myStack.peek();
                myStack.pop();
                res.add(top.val);
    
                //要先添加右结点，然后是左结点
                if(top.right!=null)
                    myStack.push(top.right);
                if(top.left!=null)
                    myStack.push(top.left);
            }
        }
    
        //递归前序遍历
        void preOrder(TreeNode root) 
        {
            if(root==null)
                return;
            else
            {
                res.add(root.val);
                preOrder(root.left);
                preOrder(root.right);
            }
        }
    }

下面是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> preorderTraversal(TreeNode* root) 
        {
            vector<int> res;
            stack<TreeNode*> skt;
            while (true)
            {
                while (root != NULL)
                {
                    res.push_back(root->val);
                    skt.push(root);
                    root = root->left;
                }
    
                if (skt.empty())
                    break;
                else
                {
                    root = skt.top()->right;
                    skt.pop();
                }
            }
            return res;
        }
    };