首页 > 其他分享 >Binary Tree Postorder Traversal

Binary Tree Postorder Traversal

时间:2023-10-14 15:45:55浏览次数:38  
标签:Binary right TreeNode Tree Traversal result curr root left

Source

Given a binary tree, return the postorder traversal of its nodes' values.

Example
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [3,2,1].

Challenge
Can you do it without recursion?

题解1 - 递归

首先使用递归便于理解。

C++ - Traversal

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */
class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: Postorder in vector which contains node values.
     */
public:
    vector<int> postorderTraversal(TreeNode *root) {
        vector<int> result;

        traverse(root, result);

        return result;
    }

private:
    void traverse(TreeNode *root, vector<int> &ret) {
        if (root == NULL) {
            return;
        }

        traverse(root->left, ret);
        traverse(root->right, ret);
        ret.push_back(root->val);
    }
};

Java - Divide and Conquer

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        if (root != null) {
            List<Integer> left = postorderTraversal(root.left);
            result.addAll(left);
            List<Integer> right = postorderTraversal(root.right);
            result.addAll(right);
            result.add(root.val);
        }

        return result;
    }
}

Java - Traversal

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private List<Integer> result = new ArrayList<Integer>();

    public List<Integer> postorderTraversal(TreeNode root) {
        if (root != null) {
            postorderTraversal(root.left);
            postorderTraversal(root.right);
            result.add(root.val);
        }
        return result;
    }
}

源码分析

递归版的太简单了,没啥好说的,注意入栈顺序。

复杂度分析

时间复杂度近似为 O(n).  

题解2 - 迭代

使用递归写后序遍历那是相当的简单,我们来个不使用递归的迭代版。整体思路仍然为「左右根」,那么怎么才能知道什么时候该访问根节点呢?问题即转化为如何保证左右子节点一定先被访问到?由于入栈之后左右节点已无法区分,因此需要区分左右子节点是否被访问过(加入到最终返回结果中)。除了有左右节点的情况,根节点也可能没有任何子节点,此时也可直接将其值加入到最终返回结果中。

C++

/**
 * 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) {
        vector<int> result;
        if (root == NULL) return result;

        TreeNode *prev = NULL;
        stack<TreeNode *> s;
        s.push(root);
        while (!s.empty()) {
            TreeNode *curr = s.top();
            bool noChild = false;
            if (curr->left == NULL && curr->right == NULL) {
                noChild = true;
            }
            bool childVisited = false;
            if (prev != NULL && (curr->left == prev || curr->right == prev)) {
                childVisited = true;
            }

            // traverse
            if (noChild || childVisited) {
                result.push_back(curr->val);
                s.pop();
                prev = curr;
            } else {
                if (curr->right != NULL) s.push(curr->right);
                if (curr->left != NULL) s.push(curr->left);
            }
        }

        return result;
    }
};

Java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        Deque<TreeNode> stack = new ArrayDeque<TreeNode>();

        if (root != null) stack.push(root);
        TreeNode prev = null;
        while (!stack.isEmpty()) {
            TreeNode curr = stack.peek();
            boolean noChild = (curr.left == null && curr.right == null);
            boolean childVisited = false;
            if (prev != null && (curr.left == prev || curr.right == prev)) {
                childVisited = true;
            }
            if (noChild || childVisited) {
                curr = stack.pop();
                result.add(curr.val);
                prev = curr;
            } else {
                if (curr.right != null) stack.push(curr.right);
                if (curr.left != null) stack.push(curr.left);
            }
        }

        return result;
    }
}

源码分析

遍历顺序为『左右根』,判断根节点是否应该从栈中剔除有两种条件,一为无子节点,二为子节点已遍历过。判断子节点是否遍历过需要排除 prev == null 的情况,因为 prev 初始化为 null. Java 中在 while 内部新建 curr 变量而不是复用 root 有一定性能提升,不知是不是 JVM 运行时优化导致的。

将递归写成迭代的难点在于如何在迭代中体现递归本质及边界条件的确立,可使用简单示例和纸上画出栈调用图辅助分析。

复杂度分析

最坏情况下栈内存储所有节点,空间复杂度近似为 O(n), 每个节点遍历两次或以上,时间复杂度近似为 O(n).  

题解3 - 反转先序遍历

要想得到『左右根』的后序遍历结果,我们发现只需将『根右左』的结果转置即可,而先序遍历通常为『根左右』,故改变『左右』的顺序即可,所以如此一来后序遍历的非递归实现起来就非常简单了。

C++

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */
class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: Postorder in vector which contains node values.
     */
public:
    vector<int> postorderTraversal(TreeNode *root) {
        vector<int> result;
        if (root == NULL) return result;

        stack<TreeNode*> s;
        s.push(root);
        while (!s.empty()) {
            TreeNode *node = s.top();
            s.pop();
            result.push_back(node->val);
            // root, right, left => left, right, root
            if (node->left != NULL) s.push(node->left);
            if (node->right != NULL) s.push(node->right);
        }
        // reverse
        std::reverse(result.begin(), result.end());
        return result;
    }
};

Java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
        if (root != null) stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode curr = stack.pop();
            result.add(curr.val);
            if (curr.left != null) stack.push(curr.left);
            if (curr.right != null) stack.push(curr.right);
        }

        Collections.reverse(result);
        return result;
    }
}

源码分析

注意入栈的顺序和最后转置即可。

复杂度分析

同先序遍历。

 

标签:Binary,right,TreeNode,Tree,Traversal,result,curr,root,left
From: https://www.cnblogs.com/lyc94620/p/17764243.html

相关文章

  • btree 与 b+tree 的区别
    btree:1.关键字和记录放在一起     2.越靠近根节点的记录查询速度越快b+tree:1.非叶子节点中只有关键字和指向下一个节点的索引,记录只放在叶子节点中      2.查询都需要从根节点走到叶子节点,叶子节点还要进行关键字的比较,每个记录的查询时间基本相同......
  • Oracle索引之(b-tree、bitmap、聚集、非聚集)
    Oracle索引之(b-tree、bitmap、聚集、非聚集)一、B-TREE索引一个B树索引只有一个根节点,它实际就是位于树的最顶端的分支节点。可以用下图一来描述B树索引的结构。其中,B表示分支节点,而L表示叶子节点。对于分支节点块(包括根节点块)来说,其所包含的索引条目都是按照顺序排列的(缺省是......
  • MEX Tree
    MEXTreeMEXTree-洛谷|计算机科学教育新生态(luogu.com.cn)目录MEXTree题目大意基本思路询问修改code题目大意给出一棵\(n\)个点的树,点从\(0\)到\(n-1\)编号。定义一条路径的权值是路径上所有点编号的\(mex\)。对于每个\(0\lei\len\)求出\(mex\)为\(i......
  • CF963B Destruction of a Tree 题解
    CF963BDestructionofaTree题解  洛谷题目链接  这里提供一个较为朴素的DP想法。题意简述  给定一棵树,节点个数不超过\(2\times10^5\),每次可以删掉度数为偶数的点。问最后能不能删完;能删完给出删除方案。思路分析  首先可以随便选一个点作为根。  其次,......
  • 动态树(Link-Cut Tree)
    算法思想动态树算法用于解决一类树上问题,涉及树边的连接和断开,并借助splay实现高效维护树上路径信息。算法细节见YangZhe的论文代码实现P3690【模板】动态树(LCT)#include<bits/stdc++.h>#definelllonglong#defineilinlineusingnamespacestd;intread(){in......
  • [gym103860D]Tree Partition
    D-TreePartition考虑将树转换到一个序列上,钦定\(1\)为根节点,\(1\)的父亲为\(0\),在序列上,孩子向父亲连边然后考虑设\(dp\)状态\(dp[i][j]\)表示前\(i\)个点,分成\(j\)段的方案数,那么\(dp[i][j]\)从\(dp[k][j-1]\)转移过来要满足以下条件之一:点\(i\)的后向边\((a,b)\)满足\(a\l......
  • JavaSE---SortedSet(TreeSet)
    SortedSet概述A{@linkSet}thatfurtherprovidesatotalorderingonitselements.提供元素排序的set;Theelementsareorderedusingtheir{@linkplainComparablenatural ordering},orbya{@linkComparator}typicallyprovidedatsortedsetcre......
  • 模型视图简介、QListWidget、QTreeWidget、QTableWidget、QStringListModel、QFileSys
    一、模型视图简介   有时,我们的系统需要显示大量数据,比如从数据库中读取数据,以自己的方式显示在自己的应用程序的界面中。早期的Qt要实现这个功能,需要定义一个组件,在这个组件中保存一个数据对象,比如一个列表。我们对这个列表进行查找、插入等的操作,或者把修改的地方写回,然后......
  • TreeAPI 递归和非递归遍历
    只包含递归和非递归遍历#include<stdio.h>#include<stdlib.h>#defineMaxSize20typedefstructnode{intdata;structnode*lchild,*rchild;}TreeNode,*Tree;typedefTreeNode*Elem;//方便修改栈中元素类型typedefstruct{Elemdata......
  • sourcetree界面卡死,改用命令行提交
    在github上创建了空仓库https://github.com/wantnon/UE-Yang-426,并clone到了本地(C:/GitHub2/UE-Yang-426),然后把自己修改过的ue4.26源码拷贝到这个路径,用sourcetree提交,结果由于一次性添加文件太多,“暂存所有”这一步sourcetree界面卡死,所以只能考虑用命令行提交了,问gpt4:于是打......