[leetcode]二叉树的后序遍历

题目描述

给定一个二叉树，返回它的后序遍历。
示例:

输入: [1,null,2,3]  
   1
    \
     2
    /
   3 

输出: [3,2,1]

算法实现

后序遍历先遍历左子树，然后遍历右子树，最后访问树的根节点

递归版(php)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($value) { $this->val = $value; }
 * }
 */
class Solution {
    public $result = [];
    /**
     * @param TreeNode $root
     * @return Integer[]
     */
    function postorderTraversal($root) {
        $this->doTraverse($root);
        return $this->result;
    }
    function doTraverse($node)
         if($node==null){
             return;
         }
        if($node->left!=null) $this->doTraverse($node->left);
        if($node->right!=null) $this->doTraverse($node->right);
        array_push($this->result,$node->val);
    }
}

迭代版(php)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($value) { $this->val = $value; }
 * }
 */
class Solution {
    public $result = [];
    public $stack = [];
    /**
     * @param TreeNode $root
     * @return Integer[]
     */
    function postorderTraversal($root) {
        if($root==null){
            return [];
        }
        $this->stack[] = $root;
        do{
            
            $node = array_pop($this->stack);
            array_unshift($this->result, $node->val);
            
            if($node->left!=null){
                $this->stack[] = $node->left;
            }
            if($node->right!=null){
                $this->stack[] = $node->right;
            }
            
        }while(!empty($this->stack));
        
        return $this->result;
    }
}

参考

二叉树的后序遍历