一、題目大意
給你一棵二叉樹的根節點 root ，回傳其節點值的 后序遍歷 ，
示例 1：
輸入：root = [1,null,2,3]
輸出：[3,2,1]
示例 2：
輸入：root = []
輸出：[]
示例 3：
輸入：root = [1]
輸出：[1]
提示：
-
樹中節點的數目在范圍 [0, 100] 內
-
-100 <= Node.val <= 100
來源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/binary-tree-postorder-traversal
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
二、解題思路
二叉樹的問題，用遞回就很簡單，分析一下用非遞回方法的思路：跟前序、中序、層序一樣都要用到堆疊，后序的順序是左 右 根，所以當一個節點值被取出來時，它的左右子節點要么不存在，要么已經被訪問過了，先將根結點壓入堆疊，然后定義一個輔助結點 head，while 回圈的條件是堆疊不為空，在回圈中，首先將堆疊頂結點t取出來，如果堆疊頂結點沒有左右子結點，或者其左子結點是 head，或者其右子結點是 head 的情況下，將堆疊頂結點值加入結果 res 中，并將堆疊頂元素移出堆疊，然后將 head 指向堆疊頂元素；否則的話就看如果右子結點不為空，將其加入堆疊，再看左子結點不為空的話，就加入堆疊，注意這里先右后左的順序是因為堆疊的后入先出的特點，可以使得左子結點先被處理，
三、解題方法
3.1 Java實作
public class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
traverse(list, root);
return list;
}
public void traverse(List<Integer> list, TreeNode root) {
if (root == null) {
return;
}
traverse(list, root.left);
traverse(list, root.right);
list.add(root.val);
}
}
四、總結小記
- 2022/10/9 上k8s是不是卷呀
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/511959.html
標籤：其他