leetCode解题报告之Binary Tree Postorder Traversal

川长思鸟来 2022-08-25 15:57 23阅读 0赞

**题目：**

### Binary Tree Postorder Traversal ###

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?

**分析：**

初看以为是很简单的递归后序遍历二叉树的结点，之后看到要返回一个ArrayList之后，感觉如果用平常的递归遍历访问二叉树结点的话，有可能会TLE或者是StackOverFlow，之后想到要用“非递归方式”后序遍历二叉树.

**解题思路：**

开一个Stack，由于root结点是最后访问的结点，所以我们先将root结点push到Stack中

我们写一个while循环，while循环结束的条件是栈中没有任何结点。

当栈中有结点的时候，我们将取出栈顶结点

1、判断下它是否是叶子结点（left和right都为null）, 如果是叶子结点的话，那么不好意思，把它弹出栈，并把值add到ArrayList中，如果不是叶子结点的话，那么

2、我们判断下它的left（node.left）是否为null,如果不为null，把它的左孩子结点push到栈中来，并把它的左孩子域设为null, 然后跳过此次循环剩下的部分

3、如果它的left 为null, 把它的右孩子结点push到栈中来，并把它的右孩子域设为null，然后跳过此次循环剩下的部分！

**图解：**

![SouthEast][]

**类似的题目：**

### Binary Tree Preorder Traversal ###

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

For example:  
Given binary tree `{1,#,2,3}`,

1
        \
         2
        /
       3

return `[1,2,3]`.

Note: Recursive solution is trivial, could you do it iteratively?

**AC代码：**

package cn.xym.leetcode.binarytree;
    
    import java.util.ArrayList;
    import java.util.Stack;
    
    
    class TreeNode {
    	int val;
    	TreeNode left;
    	TreeNode right;
    
    	TreeNode(int x) {
    		val = x;
    	}
    }
    public class Solution {
    	
    	public ArrayList<Integer> preorderTraversal(TreeNode root) {
    		
    		ArrayList<Integer> list = new ArrayList<Integer>();
    		ArrayList<Integer> list2 = new ArrayList<Integer>();
            if (root == null)
            	return list;
            Stack<TreeNode> stack = new Stack<TreeNode>();
            stack.push(root);
            while (stack.size() != 0){
            	TreeNode top = stack.peek();
            	if (top.left == null && top.right == null){
            		list.add(top.val);
            		stack.pop();
            	}
            	if (top.right != null){
            		stack.push(top.right);
            		top.right = null;
            		continue;
            	}
            	if (top.left != null){
            		stack.push(top.left);
            		top.left = null;
            		continue;
            	}
            }
            for (int i=0; i<list.size(); ++i){
            	list2.add(list.get(list.size()-1-i));
            }
            return list2;
        }
    	public static void main(String[] args) {
    		Solution sl = new Solution();
    		TreeNode root1 = new TreeNode(1);
    		TreeNode root2 = new TreeNode(2);
    		TreeNode root3 = new TreeNode(3);
    		TreeNode root4 = new TreeNode(4);
    		TreeNode root5 = new TreeNode(5);
    		TreeNode root6 = new TreeNode(6);
    		root1.left = root2;
    		root1.right = root3;
    		root2.left = root4;
    		root2.right = root5;
    		root3.left = root6;
    		
    		ArrayList<Integer> list = sl.preorderTraversal(root1);
    		System.out.println(list);
    	}
    }

[SouthEast]: /images/20220824/5a813d7ee63542e7aadfc1bf6e78f3c4.png