第四周 学习总结

用户头像
冯凯
关注
发布于: 2020 年 06 月 27 日

树相关的问题,主要有两种递归,也可以用遍历的方法完成。



二叉树的题目的方法类似,细微改动。



比如二叉树中序遍历,国际站优秀代码:



class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode curr = root ;
while (curr != null || !stack.isEmpty()){
while (curr != null){
stack.push(curr);
curr = curr.left;
}
curr = stack.pop();
res.add(curr.val);
curr = curr.right;
}
return res;
}
}



中序遍历来 判断,是否是二叉搜索树



public boolean isValidBST(TreeNode root) {
if (root == null) return true;
Stack<TreeNode> stack = new Stack<>();
TreeNode pre = null;
while (root != null || !stack.isEmpty()) {
while (root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
if(pre != null && root.val <= pre.val) return false;
pre = root;
root = root.right;
}
return true;
}



用户头像

冯凯

关注

还未添加个人签名 2020.05.26 加入

还未添加个人简介

评论

发布
暂无评论
第四周 学习总结