剑指Offer之Java算法习题精讲二叉树专题篇下

剑指Offer之Java算法习题精讲二叉树专题篇下

题目一

解法

/**

* Definition for a binary tree node.

* public class TreeNode {

* int val;

* TreeNode left;

* TreeNode right;

* TreeNode() {}

* TreeNode(int val) { this.val = val; }

* TreeNodeaPGAoUAYh(int val, TreeNode left, TreeNode right) {

* this.val = val;

* this.left = left;

* this.right = right;

* }

* }

*/

class Solution {

public int maxDepth(TreeNode root) {

return method(root);

}

int method(TreeNode root){

if(root==null){

return 0;

}

int l = method(root.left);

int r = method(root.right);

return Math.max(l, r) + 1;

}

}

题目二

解法

/**

* Definition for a binary tree node.

* public class TreeNode {

* int val;

* TreeNode left;

* TreeNode right;

* TreeNode() {}

* TreeNode(int val) { this.val = val; }

* TreeNode(int val, TreeNode left, TreeNode right) {

* this.val = val;

* this.left = left;

* this.right = right;

* }

* }

*/

class Solution {

int ans = 0;

public int diameterOfBinaryTree(TreeNode root) {

method(root);

return ans;

}

public int method(TreeNode root){

if(root==null){

return 0;

}

int l = method(root.left);

int r = method(root.right);

ans = Math.max(ans,l+r);

return Math.max(l,r)+1;

}

}

题目三

解法

/**

* Definition for a binary tree node.

* public class TreeNode {

* int val;

* TreeNode left;

* TreeNode right;

* TreeNode() {}

* TreeNode(int val) { this.val = val; }

* TreeNode(int val, TreeNode left, TreeNode right) {

* this.val = val;

* this.left = left;

* this.right = right;

* }

* }

*/

class Solution {

public int minDepth(TreeNode root) {

if(root==null) return 0;

if(root.left==null&&root.right==null) return 1;

int min = Integer.MAX_http://VALUE;

if(root.left!=null){

min = Math.min(min,minDepth(root.left));

}

if(root.right!=null){

min = Math.min(min,minDepth(root.right));

}

return min+1;

}

}

题目四

解法

/**

* Definition for a binary tree node.

* public class TreeNode {

* int val;

* TreeNode left;

* TreeNode right;

* TreeNode() {}

* TreeNode(int val) { this.val = val; }

* TreeNode(int val, TreeNode left, TreeNode right) {

* this.val = val;

* this.left = left;

* this.right = right;

* }

* }

*/

class Solution {

List list = new ArrayList();

public List preorderTraversal(TreeNode root) {

method(root);

return list;

}

public void method(TreeNode root){

if(root==null){

return;

}

// 前序

list.add(root.val);

method(root.left);

// 中序

method(root.right);

// 后序

}

}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。