算法训练营第一期 | 一套模板解决二叉树的前序、中序、后序遍历

一、题目描述

给你二叉树的根节点 root ,返回它节点值的 前序、中序、后序 遍历。

二、题目解析

三、参考代码

1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 二叉树的前序遍历( LeetCode 144) : https://leetcode-cn.com/problems/binary-tree-preorder-traversal/
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {

        // 设置一个数组用来保存二叉树前序遍历的结果
        List<Integer> preorderReslut = new ArrayList<>();

        // 设置一个数组用来保存二叉树中序遍历的结果
        List<Integer> inorderResult = new ArrayList<>();

        // 设置一个数组用来保存二叉树后序遍历的结果
        List<Integer> postorderResult = new ArrayList<>();

        // 设置一个栈,用来保存路径
        Stack<TreeNode> stack = new Stack<>();

        // 设置一个节点,一开始指向根节点
        TreeNode node = root;

        // 设置三种状态,方便表示当前遍历当前节点的时候进行到哪一步了
        // 每个节点都有 左、右、上 这三种状态
        // 按照 左 --> 右 --> 上 的顺序观察每个节点

        // 左代表该节点的左右孩子节点都没有遍历
        int nodeLeft = 100;

        // 右代表该节点的左孩子节点已经遍历,右孩子节点还没有遍历
        int nodeRight = 200;

        // 上代表左右孩子节点都已经遍历,需要返回到它的父节点
        int nodeUp = 300;

        // 每个节点的初始化状态都是从 左 开始
        int nodeState = nodeLeft;


        // 对二叉树进行遍历
        while(node != null){

            // 位置 ① 

            // 如果当前节点的状态是【左】,说明该节点的左右孩子节点都没有遍历
            if(nodeState == nodeLeft){
                // 把当前节点加入到二叉树前序遍历的结果数组中
                preorderReslut.add(node.val);

                // 如果当前节点有左子树
                if(node.left != null){

                    // 先把当前节点加入到栈中,用来记录节点移动的路径
                    stack.push(node);

                    // 开始观察当前节点的左孩子节点,代码来到了位置 ① 
                    node = node.left;
                }else{

                    // 如果当前节点没有左子树,切换当前节点的状态为【右】
                    // 代码来到了位置 ① 
                    nodeState = nodeRight;
                }

            }else if(nodeState == nodeRight){ // 如果当前节点的状态是【右】,说明该节点的左孩子节点已经遍历,右孩子节点还没有遍历

                // 把当前节点加入到二叉树中序遍历的结果数组中
                // inorderResult.add(node.val);

                // 如果当前节点有右子树
                if(node.right != null){

                    // 先把当前节点加入到栈中,用来记录节点移动的路径
                    stack.push(node);

                    // 开始观察当前节点的右孩子节点
                    node = node.right;

                    // 每个节点开始的状态都是【左】开始,所以需要重新设置一下节点的状态
                    nodeState = nodeLeft;

                    // 执行完上面三行代码,代码来到了位置 ①     

                }else{
                    // 如果当前节点没有右子树,切换当前节点的状态为【上】
                    // 代码来到了位置 ①
                    nodeState = nodeUp;
                }
            }else if(nodeState == nodeUp){ // 如果当前节点的状态是【上】,说明左右孩子节点都已经遍历,需要返回到它的父节点
                // 把当前节点加入到二叉树后序遍历的结果数组中
                //postorderResult.add(node.val);

                // 需要返回到当前节点的父节点位置,通过栈顶元素来获取当前节点的父节点
                // 首先构建一个空的节点
                TreeNode parent = null;

                // 如果栈中有元素
                if(!stack.isEmpty()){

                    // 那么,栈顶元素就是当前节点的父节点
                    parent = stack.pop();

                    // 判断一下父节点的左节点是否为当前节点
                    // 比如这颗二叉树
                    //           1
                    //         /   \
                    //        2     3
                    //       / \     \
                    //      4   5     6
                    //  如果当前节点是 4 ,那么 4 的父节点是 2,2 的左孩子节点是 4,此时需要切换状态为【右】
                    //  如果当前节点是 5 ,那么 5 的父节点是 2,2 的左孩子节点是 4,此时不需要切换状态

                    // 如果父节点的左节点为当前节点
                    if(parent.left == node){
                        // 切换当前节点的状态为【右】
                        nodeState = nodeRight;
                    }
                }
                // 开始观察当前节点的父节点
                // 如果上述代码中栈中有元素,那么 parent 有值,代码来到了位置 ①
                // 如果上述代码中栈中没有元素,那么 parent 没有值,会跳出循环
                node = parent;

            }
        }

        // 根据题目要求,返回二叉树前序、中序、后序遍历的结果
        return preorderReslut;

    }
}

2、C++ 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 二叉树的前序遍历( LeetCode 144) : https://leetcode-cn.com/problems/binary-tree-preorder-traversal/
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {

        // 设置一个数组用来保存二叉树前序遍历的结果
        vector<int> preorderReslut;

        // 设置一个数组用来保存二叉树中序遍历的结果
        vector<int> inorderResult;

        // 设置一个数组用来保存二叉树后序遍历的结果
        vector<int> postorderResult;

        // 设置一个栈,用来保存路径
        stack<TreeNode*> st;

        // 设置一个节点,一开始指向根节点
        TreeNode* node = root;

        // 设置三种状态,方便表示当前遍历当前节点的时候进行到哪一步了
        // 每个节点都有 左、右、上 这三种状态
        // 按照 左 --> 右 --> 上 的顺序观察每个节点

        // 左代表该节点的左右孩子节点都没有遍历
        int nodeLeft = 100;

        // 右代表该节点的左孩子节点已经遍历,右孩子节点还没有遍历
        int nodeRight = 200;

        // 上代表左右孩子节点都已经遍历,需要返回到它的父节点
        int nodeUp = 300;

        // 每个节点的初始化状态都是从 左 开始
        int nodeState = nodeLeft;


        // 对二叉树进行遍历
        while(node != NULL){

            // 位置 ① 

            // 如果当前节点的状态是【左】,说明该节点的左右孩子节点都没有遍历
            if(nodeState == nodeLeft){
                // 把当前节点加入到二叉树前序遍历的结果数组中
                preorderReslut.push_back(node->val);

                // 如果当前节点有左子树
                if(node->left != NULL){

                    // 先把当前节点加入到栈中,用来记录节点移动的路径
                    st.push(node);

                    // 开始观察当前节点的左孩子节点,代码来到了位置 ① 
                    node = node->left;
                }else{

                    // 如果当前节点没有左子树,切换当前节点的状态为【右】
                    // 代码来到了位置 ① 
                    nodeState = nodeRight;
                }

            }else if(nodeState == nodeRight){ // 如果当前节点的状态是【右】,说明该节点的左孩子节点已经遍历,右孩子节点还没有遍历

                // 把当前节点加入到二叉树中序遍历的结果数组中
                // inorderResult.push_back(node->val);

                // 如果当前节点有右子树
                if(node->right != NULL){

                    // 先把当前节点加入到栈中,用来记录节点移动的路径
                    st.push(node);

                    // 开始观察当前节点的右孩子节点
                    node = node->right;

                    // 每个节点开始的状态都是【左】开始,所以需要重新设置一下节点的状态
                    nodeState = nodeLeft;

                    // 执行完上面三行代码,代码来到了位置 ①     

                }else{
                    // 如果当前节点没有右子树,切换当前节点的状态为【上】
                    // 代码来到了位置 ①
                    nodeState = nodeUp;
                }
            }else if(nodeState == nodeUp){ // 如果当前节点的状态是【上】,说明左右孩子节点都已经遍历,需要返回到它的父节点
                // 把当前节点加入到二叉树后序遍历的结果数组中
                //postorderResult.add(node.val);

                // 需要返回到当前节点的父节点位置,通过栈顶元素来获取当前节点的父节点
                // 首先构建一个空的节点
                TreeNode* parent = NULL;

                // 如果栈中有元素
                if(!st.empty()){

                    // 那么,栈顶元素就是当前节点的父节点
                    parent = st.top();
                    st.pop();

                    // 判断一下父节点的左节点是否为当前节点
                    // 比如这颗二叉树
                    //           1
                    //         /   \
                    //        2     3
                    //       / \     \
                    //      4   5     6
                    //  如果当前节点是 4 ,那么 4 的父节点是 2,2 的左孩子节点是 4,此时需要切换状态为【右】
                    //  如果当前节点是 5 ,那么 5 的父节点是 2,2 的左孩子节点是 4,此时不需要切换状态

                    // 如果父节点的左节点为当前节点
                    if(parent->left == node){
                        // 切换当前节点的状态为【右】
                        nodeState = nodeRight;
                    }
                }
                // 开始观察当前节点的父节点
                // 如果上述代码中栈中有元素,那么 parent 有值,代码来到了位置 ①
                // 如果上述代码中栈中没有元素,那么 parent 没有值,会跳出循环
                node = parent;

            }
        }

        // 根据题目要求,返回二叉树前序、中序、后序遍历的结果
        return preorderReslut;

    }
};

3、Python 代码

# 登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者:程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 二叉树的前序遍历( LeetCode 144) : https://leetcode-cn.com/problems/binary-tree-preorder-traversal/
class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:

        # 设置一个数组用来保存二叉树前序遍历的结果
        preorderReslut = []

        # 设置一个数组用来保存二叉树中序遍历的结果
        inorderResult = []

        # 设置一个数组用来保存二叉树后序遍历的结果
        postorderResult = []

        # 设置一个栈,用来保存路径
        stack = list()

        # 设置一个节点,一开始指向根节点
        node = root

        # 设置三种状态,方便表示当前遍历当前节点的时候进行到哪一步了
        # 每个节点都有 左、右、上 这三种状态
        # 按照 左 --> 右 --> 上 的顺序观察每个节点

        # 左代表该节点的左右孩子节点都没有遍历
        nodeLeft = 100

        # 右代表该节点的左孩子节点已经遍历,右孩子节点还没有遍历
        nodeRight = 200

        # 上代表左右孩子节点都已经遍历,需要返回到它的父节点
        nodeUp = 300

        # 每个节点的初始化状态都是从 左 开始
        nodeState = nodeLeft


        # 对二叉树进行遍历
        while node :

            # 位置 ① 

            # 如果当前节点的状态是【左】,说明该节点的左右孩子节点都没有遍历
            if nodeState == nodeLeft :
                # 把当前节点加入到二叉树前序遍历的结果数组中
                preorderReslut.append(node.val)

                # 如果当前节点有左子树
                if node.left :

                    # 先把当前节点加入到栈中,用来记录节点移动的路径
                    stack.append(node)

                    # 开始观察当前节点的左孩子节点,代码来到了位置 ① 
                    node = node.left
                else:

                    # 如果当前节点没有左子树,切换当前节点的状态为【右】
                    # 代码来到了位置 ① 
                    nodeState = nodeRight


            elif nodeState == nodeRight:

                # 如果当前节点的状态是【右】,说明该节点的左孩子节点已经遍历,右孩子节点还没有遍历

                # 把当前节点加入到二叉树中序遍历的结果数组中
                # inorderResult.add(node.val)

                # 如果当前节点有右子树
                if node.right :

                    # 先把当前节点加入到栈中,用来记录节点移动的路径
                    stack.append(node)

                    # 开始观察当前节点的右孩子节点
                    node = node.right

                    # 每个节点开始的状态都是【左】开始,所以需要重新设置一下节点的状态
                    nodeState = nodeLeft

                    # 执行完上面三行代码,代码来到了位置 ①     

                else:
                    # 如果当前节点没有右子树,切换当前节点的状态为【上】
                    # 代码来到了位置 ①
                    nodeState = nodeUp

            elif nodeState == nodeUp : 

                # 如果当前节点的状态是【上】,说明左右孩子节点都已经遍历,需要返回到它的父节点
                # 把当前节点加入到二叉树后序遍历的结果数组中
                # postorderResult.add(node.val)

                # 需要返回到当前节点的父节点位置,通过栈顶元素来获取当前节点的父节点
                # 首先构建一个空的节点
                parent = None

                # 如果栈中有元素
                if stack :

                    # 那么,栈顶元素就是当前节点的父节点
                    parent = stack.pop()

                    # 判断一下父节点的左节点是否为当前节点
                    # 比如这颗二叉树
                    #           1
                    #         /   \
                    #        2     3
                    #       / \     \
                    #      4   5     6
                    #  如果当前节点是 4 ,那么 4 的父节点是 2,2 的左孩子节点是 4,此时需要切换状态为【右】
                    #  如果当前节点是 5 ,那么 5 的父节点是 2,2 的左孩子节点是 4,此时不需要切换状态

                    # 如果父节点的左节点为当前节点
                    if parent.left == node :
                        # 切换当前节点的状态为【右】
                        nodeState = nodeRight

                # 开始观察当前节点的父节点
                # 如果上述代码中栈中有元素,那么 parent 有值,代码来到了位置 ①
                # 如果上述代码中栈中没有元素,那么 parent 没有值,会跳出循环
                node = parent


        # 根据题目要求,返回二叉树前序、中序、后序遍历的结果
        return preorderReslut

四、动画理解(没有声音)

发表评论

邮箱地址不会被公开。 必填项已用*标注