讨论/《二叉树》 - 二叉树的前序遍历/
《二叉树》 - 二叉树的前序遍历
共 40 个回复

思路

遍历法,与递归思路一样,区别在于需要自己实现栈。
前序遍历,根节点在先: 根-左-右。
时间复杂度O(n),空间复杂度O(n)。

代码

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        while(root!=null || !stack.isEmpty()){
            while(root!=null){
                stack.push(root);
                result.add(root.val);
                root = root.left;
            }
            root = stack.pop().right;
        }
        return result;
    }
}
17

1,递归解法

下面随便画个二叉树的图。

image.png

二叉树的前序遍历顺序是:根节点→左子树→右子树

所以上图前序遍历的结果是:A→B→D→E→C→F

访问顺序如下

image.png

代码很简单

public static void preOrder(TreeNode tree) {
    if (tree == null)
        return;
    System.out.printf(tree.val + "");
    preOrder(tree.left);
    preOrder(tree.right);
}

但这题不是让打印二叉树的节点值,而是返回一个list对象,这也很简单,我们随便改一下就行了,当然修改的方式有很多,我们随便写一个来看一下

    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        preOrder(root, res);
        return res;
    }

    public void preOrder(TreeNode root, List<Integer> res) {
        if (root == null)
            return;
        //先打印当前节点,然后打印左子树,最后再打印右子树
        res.add(root.val);
        preOrder(root.left, res);
        preOrder(root.right, res);
    }

看一下运行结果

image.png


2,非递归解法

非递归我们使用一个栈就行了,一直沿着左子树遍历,他的代码也比较简单

    public void preOrder(TreeNode tree) {
        Stack<TreeNode> stack = new Stack<>();
        stack.push(tree);//压栈
        while (!stack.empty()) {
            TreeNode t1 = stack.pop();//出栈
            System.out.println(t1.val);
            if (t1.right != null) {
                stack.push(t1.right);
            }
            if (t1.left != null) {
                stack.push(t1.left);
            }
        }
    }

我们来改一下

    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        //加个边界条件判断
        if (root == null)
            return res;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);//压栈
        while (!stack.empty()) {
            TreeNode t1 = stack.pop();//出栈
            res.add(t1.val);
            if (t1.right != null) {
                stack.push(t1.right);
            }
            if (t1.left != null) {
                stack.push(t1.left);
            }
        }
        return res;
    }

来看一下运行结果

image.png


3,Morris前序遍历方式

Morris前序遍历详细可以看下《二叉树的Morris中序和前序遍历》,这是我之前写的,由于东西太多,这里就不在照搬过来,我们直接看下莫里斯前序遍历的代码

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    //首先把根节点赋值给cur
    TreeNode cur = root;
    //如果cur不为空就继续遍历
    while (cur != null) {
        if (cur.left == null) {
            //如果当前节点cur的左子节点为空,就访问当前节点cur,
            //接着让当前节点cur指向他的右子节点
            res.add(cur.val);
            cur = cur.right;
        } else {
            TreeNode pre = cur.left;
            //查找pre节点,注意这里有个判断就是pre的右子节点不能等于cur
            while (pre.right != null && pre.right != cur)
                pre = pre.right;
            //如果pre节点的右指针指向空,我们就让他指向当前节点cur,
            //然后打印当前节点cur的值,最后再让当前节点cur指向他的左子节点
            if (pre.right == null) {
                pre.right = cur;
                res.add(cur.val);
                cur = cur.left;
            } else {
                //如果pre节点的右指针不为空,那么他肯定是指向cur的,
                //表示当前节点cur和他的的左子节点都遍历完了,直接
                //让他指向他的右子节点即可。
                pre.right = null;
                cur = cur.right;
            }
        }
    }
    return res;
}

来看一下运行结果

image.png


我把部分算法题整理成了PDF文档,截止目前总共有900多页,大家可以下载阅读
链接https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取码:6666

如果觉得有用就给个赞吧,还可以关注我的LeetCode主页查看更多的详细题解

13

执行用时:0 ms, 在所有 C 提交中击败了100.00%的用户
内存消耗:5.7 MB, 在所有 C 提交中击败了85.44%的用户

发现没有人写c, 递归迭代都是beats100, 注意传参

// 递归
void travel(struct TreeNode* root, int* arr, int* size) {
    if (root != NULL) {
        arr[(*size)++] = root->val;
        travel(root->left, arr, size);
        travel(root->right, arr, size);
    }
}

int* preorderTraversal(struct TreeNode* root, int* returnSize){
    int* arr = (int*)malloc(100*sizeof(int));
    *returnSize = 0;
    travel(root, arr, returnSize);
    return arr;
}

// 迭代
int* preorderTraversal(struct TreeNode* root, int* returnSize){
    *returnSize = 0;
    int *arr = (int *)malloc(100 * sizeof(int));
    struct TreeNode *stk[100];
    int stk_top = -1;

    while (stk_top > -1 || root != NULL) {
        while (root != NULL) {
            arr[(*returnSize)++] = root->val;
            stk[++stk_top] = root;
            root = root->left;
        }
        root = stk[stk_top--];
        root = root->right;
    }
    return arr;
}
6

python 使用递归和迭代两种方法

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        # 递归
        # res = list()
        # def preordef(root):
        #     if not root: return
        #     res.append(root.val)
        #     preordef(root.left)
        #     preordef(root.right)
        # preordef(root)
        # return res

        #  迭代
        if not root: return
        res = list()
        stack, node = [], root
        while stack or node:
            while node:
                res.append(node.val)
                stack.append(node)
                node = node.left
            node = stack.pop()
            node = node.right
        return res        



6

两种方法:
1、非递归
执行用时:0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗:8.2 MB, 在所有 C++ 提交中击败了75.50%的用户

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> aa;
        if(root==NULL) return aa;
        stack<TreeNode*> mystack;
        TreeNode * p = root;
        mystack.push(p);
        while(!mystack.empty()){
            p = mystack.top(); 
            mystack.pop();
            aa.push_back(p->val);
            if(p->right) mystack.push(p->right) ;
            if(p->left) mystack.push(p->left);            
        }     
        return aa;       
    }
};

2、递归
递归执行用时:8 ms, 在所有 C++ 提交中击败了44.31%的用户
内存消耗:19.1 MB, 在所有 C++ 提交中击败了5.02%的用户

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> aa;
        if(root==NULL) return aa;
        aa.push_back(root->val);
        vector<int> bb = preorderTraversal(root->left);
        aa.insert(aa.end(),bb.begin(),bb.end());
        preorderTraversal(root->right);
        vector<int> cc = preorderTraversal(root->right);
        aa.insert(aa.end(),cc.begin(),cc.end());
        return aa;
    }
};
6

js版本:迭代版本前序遍历

class TreenNode {
    constructor(val, left, right) {
        this.val = val === undefined ? 0 : val
        this.left = left === undefined ? null : left
        this.right = right === undefined ? null : right
    }
}

/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var preorderTraversal = function(root) {
    // preorderTraversal 前序遍历
    // 前序遍历:根节点、左节点、右节点
    // 迭代法实现
    const answer = []
    const stack = []
    if (!root) {
        return answer
    }
    stack.push(root)
    while (stack.length) {
        const cur = stack.pop()
        answer.push(cur.val)
        // 依次推入右边、左边节点
        // 为什么先推入右因为我们使用的是pop、
        if (cur.right) {
            stack.push(cur.right)
        }
        if (cur.left) {
            stack.push(cur.left)
        }
    }
    return answer
};

递归版本:

class TreeNode {
    constructor (val, left, right) {
        this.val = val === undefined ? 0 : val
        this.left = left === undefined ? null : left
        this.right = right === undefined ? null : right
    }
}
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var preorderTraversal = function(root) {
    // 二叉树 前序遍历 根左右
    // 从上到下 从左到右
    const answer = []
    const traversal = (node, arr) => {
        // 递归三要求:入参、返回值、递归退出条件、递归逻辑
        if (!node) return
        arr.push(node.val)
        traversal(node.left, answer)
        traversal(node.right, answer)
    }
    traversal(root, answer)
    return answer
};
5

Java版递归法:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    List<Integer> list = new ArrayList<>();
    public List<Integer> preorderTraversal(TreeNode root) {
        helper(root);
        return list;
    }
    public void helper(TreeNode root){
        if(root == null){
            return;
        }
        list.add(root.val);
        helper(root.left);
        helper(root.right);
    }
}
4

啥问题啊,反馈也没有人回复,这么看到c#吗?

是我的代码的问题吗?

public class Solution {
 
    public  static  IList<int> ints2 = new List<int>();

    public IList<int> PreorderTraversal(TreeNode root) {

       if (root != null)
            {
                if (root.val != 0)
                    ints2.Add(root.val);
                  if (root.left != null)
                    PreorderTraversal(root.left);
                if (root.right != null)
                    PreorderTraversal(root.right);
            }


            return ints2;
    }
}

image.png
image.png

1

我们首先要明确,任何递归都能转成循环,递归的本质就是压栈

要用栈模拟递归

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> stk;
        if(!root)
        {
            return res;
        }
        stk.push(root);
        while(!stk.empty())
        {
            TreeNode* temp = stk.top();
            stk.pop();
            res.push_back(temp->val);
            if(temp->right)
            {
                stk.push(temp->right);
            }
            if(temp->left)
            {
                stk.push(temp->left);
            }
        }
        return res;
    }
};
1

morris遍历原则:
记作当前节点为cur。

1.如果cur无左孩子,cur向右移动(cur=cur.right)
2.如果cur有左孩子,找到cur左子树上最右的节点,记为mostright

  • 如果mostright的right指针指向空,让其指向cur,cur向左移动(cur=cur.left)
  • 如果mostright的right指针指向cur,让其指向空,cur向右移动(cur=cur.right)

实现了以上原则,即实现了morris遍历。

贴出代码:

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        if(root == null)
            return res;
        TreeNode cur = root;
        TreeNode morrisRight = null;
        while(cur != null){
            morrisRight = cur.left;
            if(morrisRight != null){
                //cur有左孩子,找到cur左子树的最右节点
                while(morrisRight.right != null && morrisRight.right != cur){
                    morrisRight = morrisRight.right;
                }
                //morris的右孩子为空,让morris右孩子指向cur,cur向左移动。
                if(morrisRight.right == null){
                    res.add(cur.val);
                    morrisRight.right = cur;
                    cur = cur.left;
                    continue;
                }else{
                    //mostright的right指针指向cur,让其指向空,cur向右移动
                    morrisRight.right = null;
                }
            }else{
                res.add(cur.val);
            }
            cur = cur.right;
        }
        return res;
    }
}

时间复杂度O(n),空间复杂度O(1)

1