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)!