题目地址
https://leetcode.com/problems/binary-tree-postorder-traversal/description/
题目描述
Given a binary tree, return the postorder traversal of its nodes' values.
For example:
Given binary tree {1,#,2,3},
1
\
2
/
3
return [3,2,1].
Note: Recursive solution is trivial, could you do it iteratively?
思路
相比于前序遍历,后续遍历思维上难度要大些,前序遍历是通过一个stack,首先压入父亲结点,然后弹出父亲结点,并输出它的value,之后压人其右儿子,左儿子即可。
然而后序遍历结点的访问顺序是:左儿子 -> 右儿子 -> 自己。那么一个结点需要两种情况下才能够输出:
第一,它已经是叶子结点;
第二,它不是叶子结点,但是它的儿子已经输出过。
那么基于此我们只需要记录一下当前输出的结点即可。对于一个新的结点,如果它不是叶子结点,儿子也没有访问,那么就需要将它的右儿子,左儿子压入。
如果它满足输出条件,则输出它,并记录下当前输出结点。输出在stack为空时结束。
关键点解析
- 二叉树的基本操作(遍历)
不同的遍历算法差异还是蛮大的
-
如果非递归的话利用栈来简化操作
-
如果数据规模不大的话,建议使用递归
-
递归的问题需要注意两点,一个是终止条件,一个如何缩小规模
-
终止条件,自然是当前这个元素是null(链表也是一样)
-
由于二叉树本身就是一个递归结构, 每次处理一个子树其实就是缩小了规模,
难点在于如何合并结果,这里的合并结果其实就是left.concat(right).concat(mid)
,
mid是一个具体的节点,left和right递归求出即可
代码
/* * @lc app=leetcode id=145 lang=javascript * * [145] Binary Tree Postorder Traversal * * https://leetcode.com/problems/binary-tree-postorder-traversal/description/ * * algorithms * Hard (47.06%) * Total Accepted: 242.6K * Total Submissions: 512.8K * Testcase Example: '[1,null,2,3]' * * Given a binary tree, return the postorder traversal of its nodes' values. * * Example: * * * Input: [1,null,2,3] * 1 * \ * 2 * / * 3 * * Output: [3,2,1] * * * Follow up: Recursive solution is trivial, could you do it iteratively? * */ /** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } */ /** * @param {TreeNode} root * @return {number[]} */ var postorderTraversal = function(root) { // 1. Recursive solution // if (!root) return []; // return postorderTraversal(root.left).concat(postorderTraversal(root.right)).concat(root.val); // 2. iterative solutuon if (!root) return []; const ret = []; const stack = [root]; let p = root; // 标识元素,用来判断节点是否应该出栈 while (stack.length > 0) { const top = stack[stack.length - 1]; if ( top.left === p || top.right === p || // 子节点已经遍历过了 (top.left === null && top.right === null) // 叶子元素 ) { p = stack.pop(); ret.push(p.val); } else { if (top.right) { stack.push(top.right); } if (top.left) { stack.push(top.left); } } } return ret; };LeetCode题解144.binary-tree-preorder-traversal
题目地址 https://leetcode.com/problems/binary-tree-preorder-traversal/description/ 题目描述 Given a binary tree, return the preorder traversal of its nodes' values. Example: Input: [1,null…
LeetCode题解102.binary-tree-level-order-traversal题目地址 https://leetcode.com/problems/binary-tree-level-order-traversal/description/ 题目描述 Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to…
LeetCode题解103.binary-tree-zigzag-level-order-traversal题目地址 https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/description/ 题目描述 和leetcode 102 基本是一样的,思路是完全一样的。 Given a binary tree, return the zigzag level order trav…
LeetCode题解124.binary-tree-maximum-path-sum题目地址 https://leetcode.com/problems/binary-tree-maximum-path-sum/description/ 题目描述 Given a non-empty binary tree, find the maximum path sum. For this problem, a path is defined as a…
LeetCode题解1104.path-in-zigzag-labelled-binary-tree题目地址 https://leetcode-cn.com/problems/path-in-zigzag-labelled-binary-tree/description/ 题目描述 在一棵无限的二叉树上,每个节点都有两个子节点,树中的节点 逐行 依次按 “之” 字形进行标记。 如下图所示,在奇数行(即,第一行、第三行、第五行……)中,按从左到右的顺序进行标…