剑指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; }

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

* this.val = val;

* this.left = left;

* this.right = right;

* }

* }

*/

class Solution {

int ans;

int pre;

public int getMinimumDifference(TreeNode root) {

ans = Integer.MAX_VALUE;

pre = -1;

method(root);

return ans;

}

public void method(TreeNode root){

if(root==null) return;

method(root.left);

if(pre==-1){

pre = root.val;

}else{

ans = Math.min(ans,root.val-pre);

pre = root.val;

}

http:// method(root.right);

}

}

题目二

解法

/**

* 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 findTilt(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.abs(l-r);

return l+r+root.val;

}

}

题目三

解法

/**

* 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 boolean isSubtree(TreeNode root, TreeNode subRoot) {

return dfs(root,subRoot);

}

public boolean dfs(TreeNode root, TreeNode subRoot){

if(root==null) return false;

return cheack(root,subRoot)||dfs(root.left,subRoot)||dfs(root.right,subRoot);

}

public boolean cheack(TreeNode root, TreeNode subRoot){

if(root==null&&subRoot==null) return true;

if(root==null||subRoot==null||root.val!=subRoot.val) return false;

return cheack(root.left,subRoot.left)&&cheack(root.right,subRoot.right);

}

}

题目四

解法

/**

* 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 boolean isSameTree(TreeNode p, TreeNode q) {

if(p==null&&q==null) return true;

if(p==null||q==null||q.val!=p.val) return false;

return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);

}

}

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