leetcode145. 二叉树的后序遍历

给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。

示例 1：

输入：root = [1,null,2,3]

输出：[3,2,1]

解释：

示例 2：

输入：root = [1,2,3,4,5,null,8,null,null,6,7,9]

输出：[4,6,7,5,2,9,8,3,1]

解释：

示例 3：

输入：root = []

输出：[]

示例 4：

输入：root = [1]

输出：[1]

提示：

• 树中节点的数目在范围 [0, 100] 内
• -100 <= Node.val <= 100

进阶：递归算法很简单，你可以通过迭代算法完成吗？

/**
 * Definition for a binary tree node.
 * function TreeNode(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 postorderTraversal = function(root) {
    let res = new Array();
    return postorderTraversalNode(root,res);
};
// 先遍历一组节点，然后递归地去调用他们
var postorderTraversalNode = function(node,res) {
    if(node){
        postorderTraversalNode(node.left,res);
        postorderTraversalNode(node.right,res);
        res.push(node.val);
    
    }
    return res;
};
// 迭代：用一个栈来模拟操控 二叉树的后序遍历
// 因为栈的特性是先进后出，而后序遍历又是 前后中，所以先放中，再放后，最后放前；
var postorderTraversal = function(root) { 
    let res = [];
    if(!root) return res;
    let stack = [root];
    while(stack.length){
        root = stack.pop();
        res.unshift(root.val);
        if(root.left) stack.push(root.left);
        if(root.right) stack.push(root.right); 
    }
    return res; 
};

原文地址：https://blog.csdn.net/Turboyiyi/article/details/142526410

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！