后序遍历二叉树-在线编程-K6K4.com

二叉树后序遍历的规则：
（1）后序遍历左子树

（2）后序遍历右子树

（3）访问根节点

输入、输出描述

输入：

给定一个二叉树的根节点

输出：

返回后序遍历二叉树节点序列对应的”data"属性列表

Example

输入：

二叉树如下：
    1
   / \
   2  3
  /  / \
  4  5  6

输出：

4,2,5,6,3,1

代码：

import java.util.*;

public class Main {
   public int[] solution(TreeNode<Integer> root) {

        //因为事先无法知道节点的个数，因此使用可变长度的链表存储结果
        List<Integer> list = new ArrayList<>();
        solution(root, list);

        if (list == null || list.isEmpty()) {
            return null;
        }

        int[] result = new int[list.size()];
        for (int i = 0; i < result.length; i++) {
            result[i] = list.get(i);
        }

        return result;

    }

    public void solution(TreeNode<Integer> root, List<Integer> list) {
        if (root == null) {
            return;
        }
        //递归遍历左子树
        solution(root.left, list);
        //递归遍历右子树
        solution(root.right, list);
        list.add(root.data);
    }
}