二叉树的中序遍历递归classSolution{publicListIntegerinorderTraversal(TreeNoderoot){ListIntegeransnewArrayList();inorder(root,ans);returnans;}publicvoidinorder(TreeNoderoot,ListIntegerans){if(rootnull)return;inorder(root.left,ans);ans.add(root.val);inorder(root.right,ans);}}二叉树的最大深度递归计算classSolution{publicintmaxDepth(TreeNoderoot){if(rootnull)return0;// 左右子树的最大深度 1return1Math.max(maxDepth(root.left),maxDepth(root.right));}}深度优先搜索、广度优先搜索都可以做翻转二叉树一看也是个递归问题翻转二叉树就是翻转左右子树然后依次递归翻转子树的左右子树。这里本来想通过交换左右的值来实现但是不可以比如左子树不为空右子树为空就没办法做了classSolution{publicTreeNodeinvertTree(TreeNoderoot){if(rootnull)returnnull;TreeNodetemproot.left;root.leftroot.right;root.righttemp;invertTree(root.left);invertTree(root.right);returnroot;}}对称二叉树递归classSolution{publicbooleanisSymmetric(TreeNoderoot){returnisSymmetric1(root.left,root.right);}privatebooleanisSymmetric1(TreeNodel,TreeNoder){// 如果都为空那就是相等if(lnullrnull)returntrue;// 如果一个为空一个不为空那就是不相等if(lnullr!null||l!nullrnull)returnfalse;booleanr1isSymmetric1(l.left,r.right);booleanr2isSymmetric1(l.right,r.left);returnr1r2l.valr.val;}}这两个if判断可以简化为classSolution{publicbooleanisSymmetric(TreeNoderoot){returnisSymmetric1(root.left,root.right);}privatebooleanisSymmetric1(TreeNodel,TreeNoder){// 简化if(lnull||rnull)returnlr;booleanr1isSymmetric1(l.left,r.right);booleanr2isSymmetric1(l.right,r.left);returnr1r2l.valr.val;}}迭代使用队列左队列记录左边节点右队列记录右边节点队列元素不能为空那我们在遍历的时候出现两个队列元素不相等的时候就可以直接判断不对称。classSolution{publicbooleanisSymmetric(TreeNoderoot){// 放入左右节点DequeTreeNodequeueLeftnewLinkedList(){{if(root.left!null)add(root.left);}};DequeTreeNodequeueRightnewLinkedList(){{if(root.right!null)add(root.right);}};while(queueLeft.size()queueRight.size()queueLeft.size()0){// 分别取一个元素TreeNodelqueueLeft.removeFirst();TreeNoderqueueRight.removeFirst();// 如果值不等那就不对称了if(l.val!r.val)returnfalse;// 对应节点不对称返回 falseif(l.left!nullr.rightnull||l.leftnullr.right!null)returnfalse;// 不为空则加入此时经过前面的判断现在只有都为空或者都不为空的情况if(l.left!null)queueLeft.add(l.left);if(r.right!null)queueRight.add(r.right);if(l.right!nullr.leftnull||l.rightnullr.left!null)returnfalse;if(l.right!null)queueLeft.add(l.right);if(r.left!null)queueRight.add(r.left);}returnqueueLeft.size()queueRight.size();}}有没有更简化的写法呢这好多if啊有我们可以让队列存null值取出来的时候再判断并且用一个队列就可以只要我们保证联系取出来的两个元素是对应关系就行classSolution{publicbooleanisSymmetric(TreeNoderoot){DequeTreeNodeqnewLinkedList();q.add(root.left);q.add(root.right);while(!q.isEmpty()){TreeNodelq.removeFirst();TreeNoderq.removeFirst();// 下一轮循环if(lnullrnull)continue;// 断定不对称if(lnull||rnull||l.val!r.val)returnfalse;// 存入两对判断q.offer(l.left);q.offer(r.right);q.offer(l.right);q.offer(r.left);}returntrue;}}
二叉树的中序遍历递归classSolution{publicListIntegerinorderTraversal(TreeNoderoot){ListIntegeransnewArrayList();inorder(root,ans);returnans;}publicvoidinorder(TreeNoderoot,ListIntegerans){if(rootnull)return;inorder(root.left,ans);ans.add(root.val);inorder(root.right,ans);}}二叉树的最大深度递归计算classSolution{publicintmaxDepth(TreeNoderoot){if(rootnull)return0;// 左右子树的最大深度 1return1Math.max(maxDepth(root.left),maxDepth(root.right));}}深度优先搜索、广度优先搜索都可以做翻转二叉树一看也是个递归问题翻转二叉树就是翻转左右子树然后依次递归翻转子树的左右子树。这里本来想通过交换左右的值来实现但是不可以比如左子树不为空右子树为空就没办法做了classSolution{publicTreeNodeinvertTree(TreeNoderoot){if(rootnull)returnnull;TreeNodetemproot.left;root.leftroot.right;root.righttemp;invertTree(root.left);invertTree(root.right);returnroot;}}对称二叉树递归classSolution{publicbooleanisSymmetric(TreeNoderoot){returnisSymmetric1(root.left,root.right);}privatebooleanisSymmetric1(TreeNodel,TreeNoder){// 如果都为空那就是相等if(lnullrnull)returntrue;// 如果一个为空一个不为空那就是不相等if(lnullr!null||l!nullrnull)returnfalse;booleanr1isSymmetric1(l.left,r.right);booleanr2isSymmetric1(l.right,r.left);returnr1r2l.valr.val;}}这两个if判断可以简化为classSolution{publicbooleanisSymmetric(TreeNoderoot){returnisSymmetric1(root.left,root.right);}privatebooleanisSymmetric1(TreeNodel,TreeNoder){// 简化if(lnull||rnull)returnlr;booleanr1isSymmetric1(l.left,r.right);booleanr2isSymmetric1(l.right,r.left);returnr1r2l.valr.val;}}迭代使用队列左队列记录左边节点右队列记录右边节点队列元素不能为空那我们在遍历的时候出现两个队列元素不相等的时候就可以直接判断不对称。classSolution{publicbooleanisSymmetric(TreeNoderoot){// 放入左右节点DequeTreeNodequeueLeftnewLinkedList(){{if(root.left!null)add(root.left);}};DequeTreeNodequeueRightnewLinkedList(){{if(root.right!null)add(root.right);}};while(queueLeft.size()queueRight.size()queueLeft.size()0){// 分别取一个元素TreeNodelqueueLeft.removeFirst();TreeNoderqueueRight.removeFirst();// 如果值不等那就不对称了if(l.val!r.val)returnfalse;// 对应节点不对称返回 falseif(l.left!nullr.rightnull||l.leftnullr.right!null)returnfalse;// 不为空则加入此时经过前面的判断现在只有都为空或者都不为空的情况if(l.left!null)queueLeft.add(l.left);if(r.right!null)queueRight.add(r.right);if(l.right!nullr.leftnull||l.rightnullr.left!null)returnfalse;if(l.right!null)queueLeft.add(l.right);if(r.left!null)queueRight.add(r.left);}returnqueueLeft.size()queueRight.size();}}有没有更简化的写法呢这好多if啊有我们可以让队列存null值取出来的时候再判断并且用一个队列就可以只要我们保证联系取出来的两个元素是对应关系就行classSolution{publicbooleanisSymmetric(TreeNoderoot){DequeTreeNodeqnewLinkedList();q.add(root.left);q.add(root.right);while(!q.isEmpty()){TreeNodelq.removeFirst();TreeNoderq.removeFirst();// 下一轮循环if(lnullrnull)continue;// 断定不对称if(lnull||rnull||l.val!r.val)returnfalse;// 存入两对判断q.offer(l.left);q.offer(r.right);q.offer(l.right);q.offer(r.left);}returntrue;}}
)
