[leetcode]二叉树的中序遍历

题目描述

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

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

输出: [1,3,2]

算法实现

中序遍历是先遍历左子树，然后访问根节点，然后遍历右子树。

递归版(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 preorderTraversal($root) {
        $this->doTraverse($root);
        return $this->result;
    }
    function doTraverse($node){
         if($node==null){
             return;
         }
        if($node->left!=null) $this->doTraverse($node->left);
        array_push($this->result,$node->val);
        if($node->right!=null) $this->doTraverse($node->right);
    }
}

迭代版(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
/**
 * 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 inorderTraversal($root) {
        if($root==null){
            return [];
        }
        $node = $root;
        do{
        	
            if($node!=null){
                $this->stack[] = $node;
                $node = $node->left;
            }else{
                $node = array_pop($this->stack);
                $this->result[] = $node->val;
                $node = $node->right;
            }
            
        }while(!empty($this->stack)||$node!=null);
        
        return $this->result;
    }
}

参考

二叉树的中序遍历