算法练习之二叉树的最大深度，二叉树的层次遍历 II详解编程语言

/** 
 * Definition for a binary tree node. 
 * public class TreeNode { 
 *     int val; 
 *     TreeNode left; 
 *     TreeNode right; 
 *     TreeNode(int x) { val = x; } 
 * } 
 */ 
class Solution { 
    public int maxDepth(TreeNode root) { 
        if(root==null) return 0; 
        int left = maxDepth(root.left)+1; 
        int right = maxDepth(root.right)+1; 
        int max = left>right?left:right; 
        return max; 
    } 
}

/** 
 * 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 { 
 
    /** 
     * @param TreeNode $root 
     * @return Integer 
     */ 
    function maxDepth($root) { 
        if($root == NULL) return 0; 
        $left = $this->maxDepth($root->left)+1; 
        $right = $this->maxDepth($root->right)+1; 
        $max = max($left,$right); 
        return $max; 
    } 
}

/** 
 * 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 { 
 
    /** 
     * @param TreeNode $root 
     * @return Integer 
     */ 
    function maxDepth($root) { 
        return $root == NULL ? 0 : max($this->maxDepth($root->left), $this->maxDepth($root->right)) + 1; 
    } 
}

例如： 
给定二叉树 [3,9,20,null,null,15,7], 
 
    3 
   / / 
  9  20 
    /  / 
   15   7 
返回其自底向上的层次遍历为： 
 
[ 
  [15,7], 
  [9,20], 
  [3] 
]

class Solution { 
    public List<List<Integer>> levelOrderBottom(TreeNode root) { 
 
        List<List<Integer>> lists = new ArrayList<>(); 
        if(root==null) new ArrayList<>(); 
        func(lists,root,0); 
        for(int i=0,j=lists.size()-1;i<j;i++,j--){ 
            List<Integer> tmp = lists.get(i); 
            lists.set(i,lists.get(j)); 
            lists.set(j,tmp); 
        } 
        return lists; 
    } 
 
    private void func(List<List<Integer>> lists,TreeNode root,int level){ 
 
        if(root==null) return; 
        if(lists.size()==level){ 
            List<Integer> tmp = new ArrayList<>(); 
            tmp.add(root.val); 
            lists.add(tmp); 
        }else{ 
            lists.get(level).add(root.val); 
        } 
        func(lists,root.left,level+1); 
        func(lists,root.right,level+1); 
    } 
}

class TreeNode { 
    int val; 
    TreeNode left; 
    TreeNode right; 
 
    TreeNode(int x) { 
        val = x; 
    } 
}

import java.util.List; 
 
public class Main { 
    public static void main(String[] args) { 
        Solution ss = new Solution(); 
        TreeNode root = new TreeNode(3); 
 
        TreeNode a1 = new TreeNode(9); 
        TreeNode a2 = new TreeNode(20); 
        root.left = a1; 
        root.right = a2; 
 
        TreeNode b1 = new TreeNode(15); 
        TreeNode b2 = new TreeNode(7); 
        a2.left = b1; 
        a2.right = b2; 
        List<List<Integer>> lists = ss.levelOrderBottom(root); 
        System.out.print("result----"+ lists.toString()); 
    } 
}

class TreeNode{ 
    public $val   = null; 
    public $left  = null; 
    public $right = null; 
    public function __construct($value) 
    {$this->val = $value;} 
} 
 
class Solution { 
 
    /** 
     * @param TreeNode $root 
     * @return Integer[][] 
     */ 
    public function levelOrderBottom($root) 
    { 
        if (empty($root)) { 
            return []; 
        } 
        $lists = []; 
        $lists = $this->func($lists, $root, 0); 
        for ($i = 0, $j = count($lists) - 1; $i < $j; $i++) { 
            $tmp      = $lists[$i]; 
            $lists[$i] = $lists[$j]; 
            $lists[$j] = $tmp; 
            $j--; 
        } 
        return $lists; 
    } 
 
    public function func(&$lists, $root, $level = 0) 
    { 
        if (empty($root)) { 
            return null; 
        } 
 
        if (count($lists) == $level) { 
            $lists[$level][]=$root->val; 
        } else { 
            $lists[$level][]= $root->val; 
        } 
        $this->func($lists, $root->left, $level + 1); 
        $this->func($lists, $root->right, $level + 1); 
        return $lists; 
    } 
}

//[3,9,20,null,null,15,7] 
$root = new TreeNode(3); 
 
$a1   = new TreeNode(9); 
$a2   = new TreeNode(20); 
$b1   = new TreeNode(15); 
$b2   = new TreeNode(7); 
 
$root->left  = $a1; 
$root->right = $a2; 
 
$a2->left  = $b1; 
$a2->right = $b2; 
 
$aa = new Solution(); 
$rs = $aa->levelOrderBottom($root); 
var_dump(json_encode($rs));